2021 資訊之芽手寫作業 10
Deadline: None
Fenwick tree (Binary indexed tree)
這裡介紹區間元素總和問題：「給定一個長度為 n 的序列，q 次詢問區間 [a, b] 的
總和」，該問題一直都是非常經典的資料結構問題，一個簡單的做法便是預處理序列
的「前綴和」，這是因為我們發現，
「區間 [a, b] 的總和」可以轉成「區間 [1, b] 的總和」
減掉「區間 [1, a
− 1] 的總和」。也因此，只需要預處理所有區間 [1, i] 的總和，便能在
O(1)
的時間內回答任意區間 [a, b] 的總和。不過，靜態的詢問往往滿足不了資訊科學
家的野心，也因此出現了「動態區間和」的問題，也就是在多次的詢問區間和之間穿
插元素值的修改，透過前綴和的轉換，我們可以把問題簡化成：如何快速的求得一個
陣列的前綴和，以及更改其中一個元素的值？
Fenwick tree 是一個處理前綴時很有效率的資料結構，他也被稱為 Binary indexed
tree，或簡稱 BIT，在中國被稱做樹狀數组。以下我們都簡稱它為 BIT。對於一個長
度為 n 的陣列，BIT 可以在 O(n) 的時間初始化，在 O(log n) 時間詢問一個前綴的訊
息 (例如前綴和)，以及在 O(log n) 的時間修改其中一個值。BIT 的時間常數比大多
數能維護區間訊息的資料結構都來得小 (時間複雜度會把常數拿掉，但實際上還是有
影響的)，空間也非常小 (只需要多開一個大小恰好為 n 的陣列即可)，程式碼也非常
精簡 (初始化 + 修改 + 詢問，全部約 20 行)。一般來說，如果問題的性質可以使用
BIT，效率會和使用其他區間資料結構有明顯的差別。當然，BIT 的缺點就是有些問
題無法轉為前綴之間的運算，例如區間 [a, b] 的最大值就無法由區間 [1, b] 和 [1, a
− 1]
的最大值算出，這時候就無法使用它了。以下將詳細介紹 BIT 的操作。
首先，我們先介紹一個函數：lowbit(x)，表示 x 在二進位表示時，最接近 LSB(Least
Significant Bit)，也就是最靠右邊的 1 所對應的值。例如十進位下的數字 6
(10)
，在二
進位的寫法是 110
(2)
，其中的兩個 1 分別表示 2
2
和 2
1
，因此 lowbit(6) = 2
1
= 2
。同
理，20
(10)
= 10100
(2)
，所以 lowbit(20) = 2
2
= 4
。lowbit 函數可以用位元運算在 O(1)
時間內得到，在作業中會再多做說明。
為了快速回答問題又能動態修改，BIT 先記錄了一些區間的訊息，並由這些預先
處理過的區間拼出真正詢問的區間，而在單點修改時，也要另外修改包含該點的區
間。假設原始陣列長度為 n，且索引值為 1 至 n(1-based)，BIT 只需記錄恰好 n 個
區間。BIT 的這 n 個區間的右界即是 1 到 n，若一個區間的右界為 x，其左界就是
x
− lowbit(x) + 1。意即，BIT 的區間集合為
{ [x − lowbit(x) + 1, x] | 1 ≤ x ≤ n }
畫成圖之後可以發現，BIT 其實是棵刪除掉一些區間的遞迴樹 (各位在做 Merge
sort 時應該會寫出類似的樹狀結構)，如下圖所示：
1
2021 資訊之芽手寫作業 10
Deadline: None
因為每個範圍的右界都不同，我們可以只使用右界來表示這些區間，並以 range(x)
表示，也就是
range(x) = [x
− lowbit(x) + 1, x]
以下我們用前綴和當例子：已知一個長度為 n 的陣列 arr，我們希望建立一個
BIT 的陣列 bit，並滿足 bit[x] 為 arr 陣列中相對應範圍的元素和，即：
bit[x] =
∑
i
∈range(x)
arr[i] =
x
∑
i=x
−lowbit(x)+1
arr[i]
定義完 range(x) 和 bit[x] 之後，我們討論三種操作：詢問，單點修改，以及初始
化時，如何快速的得到答案或完成操作。
1. 詢問前綴和
詢問 [1, x] 的區間和很容易，因為該區間可以拆成 [1, x
−lowbit(x)] 和 [x−lowbit(x)+
1, x]
兩個區間和的加總。區間 [x
− lowbit(x) + 1, x] 的和就是 bit[x]，另外一個區
間則遞迴處理。由於 x
− lowbit(x) 在二進位表示法中會比 x 少一個 1，因此最多遞
迴
⌈log
2
x
⌉ 次之後就會終止，詢問的複雜度也就是 O(log n)。(雖然概念上另外一個
區間是遞迴處理，實作時只要使用迴圈就可以了，這也是 BIT 常數比較小的原因
之一。)
1
int
query(
int
x) {
2
int
sum = 0;
3
for
(
int
i = x; i > 0; i -= lowbit (i))
4
sum += bit[i];
5
return
sum;
6 }
2. 單點修改
將 arr[x] 的值增加 val 之後，bit 陣列中所有對應區間包含 x 的值都要改變。由
BIT 的結構圖可以觀察到，需要更新的區間為 range(x), range(x + lowbit(x)),
· · · 。
因為每往上遞迴一次，對應區間大小就會變為原本的 2 倍，因此最多遞迴
⌈log
2
n
⌉
次之後就會終止，單點修改的複雜度也就是 O(log n)。
1
void
update (
int
x,
int
val) {
2
for
(
int
i = x; i <= n; i += lowbit (i))
3
bit[i] += val;
4 }
2
2021 資訊之芽手寫作業 10
Deadline: None
3. 初始化
和詢問的操作類似，我們可以使用已經計算好的 bit[x] 值來計算未知的 bit[x] 值。
令 x 由小到大計算 bit[x]，由定義，
bit[x] =
x
∑
i=x
−lowbit(x)+1
arr[i] = arr[x] +
x
−1
∑
i=x
−lowbit(x)+1
arr[i]
除了 arr[x] 這項以外，區間內其餘元素的和可以用前面已經算好的 bit 較快的得
到答案，如 bit[8] = arr[8] + bit[7] + bit[6] + bit[4]。此做法雖然看起來計算單一
個 bit[x] 的時間複雜度不是 O(1)，但是總時間複雜度計算之後是 O(n)。演算法程
式碼如下：
1
void
init(
int
n) {
2
for
(
int
x = 1; x <= n; ++x) {
3
bit[x] = arr[x];
4
int
y = x - lowbit (x);
5
for
(
int
i = x -1; i > y; i -= lowbit (i))
6
bit[x] += bit[i];
7
}
8 }
另一個做法則是計算完 bit[x] 之後，「主動」往上更新上一層的值。該做法和上一
個做法原理完全一樣，由程式碼就可以輕易看出這是個 O(n) 的演算法：
1
void
init2(
int
n) {
2
for
(
int
x=1; x<=n; ++x)
3
bit[x] = 0;
4
for
(
int
x=1; x<=n; ++x) {
5
bit[x] += arr[x];
6
int
y = x + lowbit (x);
7
if
(y <= n) arr[y] += arr[x];
8
}
9 }
3
2021 資訊之芽手寫作業 10
Deadline: None
習題
1. (10 pts) 請證明在二補數系統下 (即
−x ≡ ~x + 1)，lowbit(x) = x&(−x)。(假設
x > 0)
。
2. 有一個初始化 BIT 的方法是一開始先把 bit 陣列歸零，並對於 arr 陣列中的每個
元素都呼叫一次 update(x, arr[x])，如以下程式碼所示：
1
void
init3(
int
n) {
2
for
(
int
x=1; x<=n; ++x)
3
bit[x] = 0;
4
for
(
int
x=1; x<=n; ++x)
5
update (x, arr[x]);
6 }
這個演算法的時間複雜度顯然是 O(n log n)，然而這只是一個上界，實際上也許並
不會那麼差，因為更新時不一定會改到滿滿的 log n 個區間，也許均攤後也是 O(n)
呢！對此我們需要更細的計算一下，以下將證明該做法的複雜度是 Ω(n log n)，也
就是均攤之後還是比較差。
為了方便起見，先假設 n = 2
m
，其中 m 為非負整數。令 f (m) 表示當 arr 長度為
2
m
時，用這個初始化做法需要更新幾次區間，也就是操作次數。由 BIT 的結構可
以發現，大小為 2
m
的 BIT 最上層一定是區間 [1, 2
m
]
，且不論更改哪個位置的值，
這個區間一定會被更改到。將最上層的區間拿走之後，下面剩下的剛好是大小為
2
m
−1
, 2
m
−2
,
· · · , 2
1
, 2
0
的 BIT，於是就得到
f (m) = 2
m
+
m
−1
∑
k=0
f (k),
f (0) = 1
(a) (10 pts) 請證明：
n
∑
i=0
i
· 2
i
−1
= (n
− 1) · 2
n
+ 1
, for m
≥ 0。
(b) (20 pts) 請證明：f (m)
≥ m · 2
m
−1
, for m
≥ 0。(即：f(m) ≥
n
2
· log
2
n , for
n = 2
m
, m
≥ 0)
3. 考慮一個無修改的區間最大值問題，雖然一段區間的最小值無法由兩個前綴的最小
值得到，但是有個人提出了以下使用 BIT 的作法：
(1) bit[x] 存的值為 range(x) 中的最大值
(2) 使用 query(a, b) 遞迴詢問一段區間 [a, b] 的最大值，實作方式為
query(a, b) =
−∞
, if a > b
max(bit[b], query(a, b
− lowbit(b))) , if b − lowbit(b) + 1 ≥ a
max(arr[b], query(a, b
− 1))
, otherwise
對於該做法，請回答下列問題：
4
2021 資訊之芽手寫作業 10
Deadline: None
(a) (10 pts) 請給出一組會讓時間複雜度超過 O(log n) 的詢問。
(b) (15 pts) 請問該做法中，詢問的時間複雜度為何？
4. 給定原始陣列 arr，我們定義一個差分陣列 dif，滿足
dif[x] =
{
arr[1]
, if x = 1
arr[x]
− arr[x − 1] , if x ̸= 1
接著再定義另外一個陣列 dif2，滿足
dif2[x] = dif[x]
× x
並且定義以下函式，時間複雜度皆為 O(log n)，可以想像內部就是用 BIT 實作的：
• query(dif, x)：回傳
x
∑
i=1
dif[i] 的值
• query(dif2, x)：回傳
x
∑
i=1
dif2[i] 的值
• update(dif, x, val)：將 dif[x] 的值加上 val
• update(dif2, x, val)：將 dif2[x] 的值加上 val
請回答以下問題：
(a) (10 pts) 請問如何使用給定的函式，在 O(log n) 時間內得到 arr[x] 的值？
(b) (15 pts) 現在將 arr 陣列中的一段區間 [a, b] 內的數都加上 val，請問如何在
O(log n)
時間內，使用給定的函式改變 dif 和 dif2 陣列以滿足定義？
(c) (15 pts) 請以 dif 陣列表示 arr 陣列的前綴和，也就是
x
∑
i=1
arr[i]。(答案中可
以有很多項 dif[i]，甚至包含
∑
，只要能表示就可以了。)
(d) (15 pts) 請使用給定的函式，在 O(log n) 時間內得到
x
∑
i=1
arr[i]。
5