$$\mathrm{二}\mathrm{元}\mathrm{索}\mathrm{引}\mathrm{樹}$$

$$\mathrm{口}\mathrm{頭}\mathrm{報}\mathrm{告}$$

$\mathrm{影}\mathrm{片}$

$\mathrm{簡}\mathrm{報}$

連結

$$\mathrm{主}\mathrm{題}\mathrm{介}\mathrm{紹}$$

$\mathrm{資}\mathrm{料}\mathrm{結}\mathrm{構}\mathrm{簡}\mathrm{介}$

二元索引樹是一個提供高效前綴和查詢，並且支援率支援單點或區間修改的資料結構。

他有以下稱呼：

• [中] 二元索引樹
• [中] 樹狀數組
• [英] Binary Indexed Tree
• [英] Fenwick Tree

$\mathrm{學}\mathrm{習}\mathrm{動}\mathrm{機}$

時常可以在程式題目中，遇到需求得一陣列之前綴和或區間和之情況。

為了方便說明，我們首先定義一些符號。令

$\{a_n{\}}_{n=1}^N$ 為一長度為

$N\in \mathbb{N}$ 之有限數列，並令

$S_n=\sum _{i=1}^n{a}_i$ 為此數列之前

$n$ 項和；令

$a,b\in \mathbb{N}$ 且

$1\le a\le b$ ，則

$S_{[a,b]}=\sum _{n=a}^b{a}_n$ 為此數列之第

$a$ 至第

$b$ 項 (首尾皆包含) 和。

求得前

$n$ 項和最 Naive 的算法就是從第一項走訪 (遍歷) 至第

$n$ 項，並把經過的所有元素加總。

然而，以上的算法有著

$\text{O}(n)$ 的時間複雜度，耗費大量時間與資源，
所以我們應該追求更高效率的算法。在這學期的課程中，我們學到動態規劃 (Dynamic Programming) ，此時就可以派上用場。

前

$n$ 項和可以被拆解成兩個子問題：前

$n-1$ 項和以及第

$n$ 項元素。或者，也就是說：

$$S_n=S_{n-1}+a_n\mathrm{\forall }n\in \mathbb{N}\wedge n\ge 2$$

因此，我們可以透過事前花費線性時間 (

$\text{O}(n)$) 建構前綴和數列

$\{p_n{\}}_{n=1}^N$ ，此數列的第

$n$ 項即代表數列

$\{a_n\}$ 的前

$n$ 項和。也就是說：

$$p_n=S_n=\sum _{i=1}^n{a}_i\mathrm{\forall }n\in \mathbb{N}$$

當前綴和數列

$\{p_n\}$ 建構好後，我們就可以達成常數時間 (

$\text{O}(1)$) 的任意前綴之查詢。

而當我們可以做到常數時間下的前綴和查詢，我們也就可以做到常數時間的任意區間和查詢，因為任意區間和皆可拆解為兩個前綴和之差。例如，數列的第

$a$ 項至第

$b$ 項之和，可以透過前

$b$ 項和減去前

$a-1$ 項和求得。也就是說

$$S_{[a,b]}=S_b-S_{a-1}=p_b-p_{a-1}\mathrm{\forall }a,b\in \mathbb{N}\wedge 1<a\le b$$

而

$p_b$ 及

$p_{a-1}$ 的取得都可以在常數時間做到，因此求得數列任意區間和的時間複雜度仍然是常數時間。

發現問題

前綴和陣列看似完美的解決了這個問題，但實際上他有個致命傷。當原數列

$\{a_n\}$ 發生變動時，前綴和數列

$\{p_n\}$ 的一部分就會立刻失效，需要更新。

更精確地說，當原數列

$\{a_n\}$ 的第

$i$ 項元素 (

$a_i$) 發生更動時，前綴和數列的第

$i$ 項之後 (包含) ，也就是第

$i$ 到第

$N$ 項都將失效，需要重新建構。

在最糟糕的情況下 (worst case) ，也就是原數列

$\{a_n\}$ 的第

$1$ 項發生更動，則整個前綴和數列

$\{p_n\}$ 都會失效，需要從頭到尾重新建構，因此將花費線性時間 (

$\text{O}(n)$) 。

然而，這也就是二元索引樹所想要解決的問題。我們希望能在時間複雜度小於

$\text{O}(n)$ 下對原數列

$\{a_n\}$ 進行修改，並維持前綴和的正確性。

二元索引樹的誕生，使我們可在做到

$\text{O}(\log n)$ 的前綴和查詢，並且支援

$\text{O}(\log n)$ 的原數列單點或區間修改。詳細原理會在下個部分說明。

此外，二元索引樹的空間只要

$n$，比線段樹的

$4n$ 小。並且和前綴和陣列一樣，只需要用一個一維陣列就可儲存一棵二元索引樹。

$\mathrm{重}\mathrm{要}\mathrm{操}\mathrm{作}$

在這個部分中，我會介紹以下二元索引樹的重要操作：

• 前綴和查詢 Prefix Sum Quries
• 單點修改 Point Updates
• 建構 Construction

前綴和查詢

$\text{Prefix Sum Queries}$

$\mathrm{操}\mathrm{作}\mathrm{流}\mathrm{程}$

關於如何建構一棵二元索引樹，我會在後面介紹。
我會以倒敘法的方式說明，使你可以更好的理解二元索引樹。

以下是一棵建構好的二元索引樹

[圖片來源：師大附中競程國手 WiwiHo 樹狀數組資料結構筆記]

令其為

$\mathbf{BIT}$ ，且令

${\mathbf{BIT}}_i$ 為

$\mathbf{BIT}$ 之第

$i$ 個節點；令

$b_i$ 為

${\mathbf{BIT}}_i$ 之權重。

則求得前

$n$ 項和的方法為：
「將第

$n$ 號節點至根節點 (第

$0$ 號節點；不包含) 之最短路徑上所有節點之權重加總」

也就是說，令

$\{P_i^n\}$ 為此二元索引樹第

$n$ 號節點至其根節點之路徑上的所有節點之有序集合、

$P_i^n$ 為此集合中第

$i$ 個節點之權重，則

$$S_n=\sum \{P_i^n\}$$

舉例來說，若想求數列

$\{a_n\}$ 的前

$7$ 項和，則我們只要將

$\mathbf{BIT}$ 之第

$7$ 號節點至根節點之最短路徑上所有節點之權重加總，就會是所求。更嚴謹地表示：

$$P^7=\{{\mathbf{BIT}}_7,{\mathbf{BIT}}_6,{\mathbf{BIT}}_4\}$$

因此

$$S_7=\sum \{P_i^7\}=b_7+b_6+b_4$$

也就是說，數列

$\{a_n\}$ 的前

$7$ 項和

$S_7$ 就會是其二元索引樹的第

$7$ 號、第

$6$ 號及第

$4$ 號節點的權重總和。

而若將此流程從圖的角度拉回二元索引樹的名字本身，其實向上追朔母節點的行為在二進制的世界中，就等同於移除目前節點索引值的「最低有效為 (Least Significant Bit) 」。

再次使用上述的例子，若想求數列前

$7$ 項和，則：

1. 先將二元索引樹第
   $7$ 號節點之權重計入總和。
2. 再將
   $7_{10}\equiv 011$
   $1$
   ${}_2$ 的最低有效為 (也就是
   $1$) 移除。
3. 得到
   $6$ ，故將第
   $6$ 號節點之權重加入總和。
4. 再將
   $6_{10}\equiv 01$
   $1$
   $0_2$ 之最低有效為 (也就是
   $2$) 移除。
5. 得到
   $4$ ，故將第
   $4$ 號節點之權重加入總和。
6. 再將
   $4_{10}\equiv 0$
   $1$
   ${00}_2$ 之最低有效為 (也就是
   $4$) 移除。
7. 得到
   $0$ ，代表我們追朔到了根節點，因此操作結束。

最後所得總和即為數列之前

$7$ 項和。

$\mathrm{運}\mathrm{作}\mathrm{原}\mathrm{理}$

給定一棵建構好的二元索引樹，能透過以上方法求得前綴和之原因將在此部分解答。

與前綴和陣列類似的是，二元索引樹的每個節點都有其所付責儲存的數列區間和。每個節點負責的區間皆與其索引值之二進制表示法有關，具體規則如下：

1. 各節點所負責的區間長度洽為其索引值之最小為元
2. 各節點所負責區間為從自身索引值往下延伸最小為元長

更精確地敘述令

$I_i$ 為

${\mathbf{BIT}}_i$ 所負責之區間，則

$$I_i=[i-\text{lsb}(i)+1,i]$$

其中，

$\text{lsb}(i)$ 代表

$i$ 的最低有效位。

因此，我們也得知

$$b_i=S_{I_i}=S_{[i-\text{lsb}(i)+1,i]}$$

舉例來說：

• 二元索引樹的第
  $7$ 號節點所負責的區間長度是
  $1$ ，也就是其最低有效為 (
  $7_{10}\equiv 011$
  $1$
  ${}_2$)。因此其所負責儲存的數列區間和為
  $S_{[7,7]}$
• 二元索引樹的第
  $6$ 號節點所負責的區間長度是
  $2$ ，也就是其最低有效為 (
  $6_{10}\equiv 01$
  $1$
  $0_2$)。因此其所負責儲存的數列區間和為
  $S_{[5,6]}$
• 二元索引樹的第
  $4$ 號節點所負責的區間長度是
  $4$ ，也就是其最低有效為 (
  $4_{10}\equiv 0$
  $1$
  ${00}_2$)。因此其所負責儲存的數列區間和為
  $S_{[1,4]}$

所以你可以觀察到，在上個部分的例子中，我們得到

$S_7=b_7+b_6+b_4$ ，而在這個部分我們又得到

$b_7=S_{[7,7]},b_6=S_{[5,6]},b_4=S_{[1,4]}$，因此我們可以驗證

$$b_7+b_6+b_4=S_{[7,7]}+S_{[5,6]}+S_{[1,4]}=S_{[1,7]}=S_7$$

的正確性。

經簡單觀察我們就可以發現，從第

$n$ 號節點持續移除節點索引值之最低有效位直到

$0$ ，經過的所有節點負責的區間和聯集就恰會是

$[1,n]$ ，而這就是加總所有路徑上節點權重就會是數列前

$n$ 項和之原理。

$\mathrm{單}\mathrm{點}\mathrm{修}\mathrm{改}\text{ Point Updates}$

$\mathrm{運}\mathrm{作}\mathrm{原}\mathrm{理}$

當原數列

$\{a_n\}$ 的第

$i$ 項元素

$a_i$ 發生更動，我們無需徹底重建二元索引樹。我們只需要更新所有負責區間覆蓋 (或包含) 到

$i$ 的節點權重。

$\mathrm{操}\mathrm{作}\mathrm{流}\mathrm{程}$

要找到所有被變動的

$a_i$ 所影響到的節點，方法與做前綴和查詢時相反，也就是要持續加上節點索引值之最低有效位。

舉例來說，當

$a_7$ 發生更動時，找到所有影響到的節點流程如下：

1. ${\mathbf{BIT}}_7$ 必受影響，對其做與
   $a_7$ 相同更新
2. 將
   $7$ 加上其最低有效位，也就是
   $1$ (
   $7_{10}\equiv 011$
   $1$
   ${}_2$) 。
3. 得到
   $8$ ，故
   ${\mathbf{BIT}}_8$ 受到影響，對其作相同更新。
4. 將
   $8$ 加上其最低有效位，也就是
   $8$ (
   $8_{10}\equiv$
   $1$
   ${000}_2$) 。
5. 得到
   $16$ ，故
   ${\mathbf{BIT}}_{16}$ 受到影響，對其作相同更新。
6. 將
   $16$ 加上其最低有效位，也就是
   $16$ (
   ${16}_{10}\equiv$
   $1$
   ${0000}_2$) 。

重複執行以上流程，直到索引值超出數列

$\{a_n\}$ 的範圍。

$\mathrm{建}\mathrm{構}\text{ Construction}$

建構一棵基於數列

$\{a_n\}$ 的二元索引樹非常簡單。

只需要先將二元索引樹所有節點權重初始化為零，意即當作數列

$\{a_n\}$ 一開始全為

$0$ ，隨後再對數列

$\{a_n\}$ 的每個元素做單點更新。

$$\mathrm{使}\mathrm{用}\mathrm{範}\mathrm{例}$$

這裡提供一題裸題，沒有額外包裝。但實際上二元索引樹常常可在求區間和但時間限制較高的情況下派上運場。

如果想嘗試解題，可以將程式碼繳交至 ZeroJudge d799 。

$\mathrm{題}\mathrm{幹}\mathrm{敘}\mathrm{述}$

給你

$N$ 個數據，不斷地改變這

$N$ 個數據的同時，也不停地問你某個區間中所有元素總合。

$\mathrm{輸}\mathrm{入}\mathrm{說}\mathrm{明}$

只有一筆測試數據。

第一行有一個數

$N$ (

$0<N\le 500000$) 。
第二行有

$N$ 個數

$a_i$ (

$1\le 1\le N\wedge 0\le a_i\le 32767$)。

第三行有一個數

$Q$ (

$0<Q\le 500000$) 。

接下來有

$Q$ 組要求和詢問。
每組要求或詢問中：

首先有一個數

$v$ (

$v\in \{1,2\}$)。

若

$v=1$ 則表示是要求，
接下來會有三個數

$x,y,k$ (

$0<x\le y\le N\wedge 0\le k\le 1000$)，表示從第

$x$ 個數據至第

$y$ 個數據，每個都加上

$k$ 。

若

$v=2$ 則表示是詢問，
接下來有兩個數

$x,y$ (

$0<x\le y\le N$)，表示詢問從第

$x$ 個數據至第

$y$ 個數據的所有元素之總和。

$\mathrm{輸}\mathrm{出}\mathrm{說}\mathrm{明}$

如果是要求，則無須輸出；

如果是詢問，則需輸出所詢問的區間元素總和。

題目來源：ZeroJudge d799

$$\mathrm{資}\mathrm{料}\mathrm{結}\mathrm{構}\mathrm{比}\mathrm{較}$$

二元索引樹和 堆積 (Heap) 有著異曲同工之妙。

堆積總是一棵完全樹。即除了最底層，其他層的節點都被元素填滿，且最底層儘可能地從左到右填入。

雖兩者運作方式不同，但相同的是，節點索引值連續 (沒有空洞) ，且子母節點關係明確，故都非常適合以陣列儲存。

另外，值得注意的是，堆積名字中沒有「二元」等字詞，但他是一棵完全二元樹；相反地，二元索引樹雖然名字中有「二元」，但他明顯並不是二元樹，因為名字中的二元是指「二進制」。

$$\mathrm{程}\mathrm{式}\mathrm{實}\mathrm{作}$$

$\mathrm{儲}\mathrm{存}\mathrm{方}\mathrm{式}\text{ Storage}$

一個基於長度為

$N$ 之數列所建構的

$\mathbf{BIT}$ 必恰有

$N$ 個節點，且母節點與子節點之間編號關係明確，都是差一個最低有效位。

此外，二元索引樹的節點索引值是連續的，中間不會有空洞。

因此，

$\mathbf{BIT}$ 非常適合以「陣列」形式儲存。

Pseudo Code

N = 16
BIT = [ 0 ] * N

$\mathrm{前}\mathrm{綴}\mathrm{和}\mathrm{查}\mathrm{詢}\text{ Prefix Sum Quries}$

流程：
將索引值持續減去其本身的最低有效位 (Least Significant Bit) ，並將所有經過節點權重相加，直到索引值被減至

$0$ 為止。

只需要一個簡單的 while 迴圈就可以實現這個流程。

Pseudo Code

def query(i):
    sum = 0
    while i > 0:
        sum += BIT[i]
        i -= lsb(i)
    return sum

$\mathrm{單}\mathrm{點}\mathrm{修}\mathrm{改}\text{ Point Updates}$

流程：
將索引值持續加上其本身的最低有效位 (Least Significant Bit) ，並將所有經過節點做相同更新，直到索引值被加至超過

$N$ 為止。

Pseudo Code

def update(i, delta):
    while i <= N:
        BIT[i] += delta
        i += lsb(i)

$\mathrm{二}\mathrm{進}\mathrm{制}\mathrm{最}\mathrm{低}\mathrm{有}\mathrm{效}\mathrm{位}\text{ Least Significant Bit}$

取得最小位元最簡單的方法是取

$x$ 和

$-x$ 的

$\text{bitwise and}$ 。
因為

$-x$ 是

$x$ 的補數

$+1$ (Two's Complement)。

def lsb(x):
    return x & -x

$\mathrm{完}\mathrm{整}\mathrm{範}\mathrm{例}\mathrm{程}\mathrm{式}\mathrm{碼}$

以下以 C++ 實作二元索引樹，作為範例程式碼。

#include <bits/stdc++.h>

using namespace std;

const int N = 16;
int BIT[N] = {0};

int lsb(int x) {
    /* Returns the least significant bit of x */
    return x & -x;
}

int prefix(int n) {
    /* Returns the n-th prefix sum */
    int sum = 0, idx = n;
    while (idx > 0) {
        // cout << "i: " << idx << endl;
        sum += BIT[idx-1];
        idx -= lsb(idx);
    }
    return sum;
}

int query(int l, int r) {
    /* Return the range sum of the interval [l, r] */
    if (l == 1) return prefix(r);
    return prefix(r) - prefix(l-1);
}

void update(int idx, int delta) {
    /* Updates the idx-th element of the array */
    while (idx <= N) {
        BIT[idx-1] += delta;
        idx += lsb(idx);
    }
}

int main() {
    srand(time(nullptr));
    cout << "Random Array: " << endl;
    cout << "[ ";
    for (int i = 1; i <= N; ++i) {
        int a = (rand() % 21) * (rand() % 10 > 4 ? 1 : -1);
        cout << a << ' ';
        update(i, a);
    }
    cout << "]" << endl;
    
    int l, r;
    cout << "Enter Your Query [l, r] (-1 to quit): " << endl;
    while (true) {
        cout << "l: "; cin >> l;       
        if (l == -1) break;
        cout << "r: "; cin >> r;
        if (r == -1) break;
        cout << "Range sum of [" << l << ", " << r << "] is " << query(l, r) << endl;
    }

    return 0;
}

Source Code Gist

$$\mathrm{複}\mathrm{雜}\mathrm{度}\mathrm{分}\mathrm{析}$$

$\mathrm{前}\mathrm{綴}\mathrm{和}\mathrm{查}\mathrm{詢}\text{ Prefix Sum Queries}$

流程為持續移除最低有效位直至

$0$ ，而在範圍內的節點索引值最多可以有

$\lfloor {\log }_{2}N\rfloor$ 個有效位元。最多也只可能移除

$\lfloor {\log }_{2}N\rfloor$ 次才追朔到根節點。

因此，前綴和查詢的時間複雜度為

$\text{O}(\log n)$ 。

$\mathrm{單}\mathrm{點}\mathrm{修}\mathrm{改}\text{ Point Updates}$

流程為持續加上最低有效位直至超出範圍。在最糟的情況下，如果從

$1$ 開始加，最多也只可能加上

$\lceil {\log }_{2}N\rceil$ 才超出或剛好到範圍邊界。

因此，前單點修改的時間複雜度為

$\text{O}(\log n)$ 。

$\mathrm{建}\mathrm{構}\text{ Construction}$

流程為先將二元索引樹所有節點權重初始化為零，意即當作數列

$\{a_n\}$ 一開始全為

$0$ ，隨後再對數列

$\{a_n\}$ 的每個元素做單點更新。

在以上方法中，共有

$n$ 次更新，而每次更新複雜度是

$\text{O}(\log n)$ 。
因此，建構一棵二元索引樹的時間複雜度為

$\text{O}(n\log n)$

[註：事實上，二元索引樹的建構是可以在

$\text{O}(n)$ 內完成的，請參考 Fenwick Tree construction]

$$\mathrm{參}\mathrm{考}\mathrm{資}\mathrm{料}\text{ References}$$

• 師大附中競程國手 WiwiHo 樹狀數組資料結構筆記
• WilliamFiset 的 Fenwick Tree Youtube 教學影片系列（播放清單）
• ZeroJudge d799 区间求和
• Youtube Video - One's Complement, Two's Complement, and Signed Magnitude