Fenwick Tree

Fenwick Tree 又稱 Binary Indexed Tree(樹狀數組)，以下簡稱 BIT，是一個方便解決區間與前綴和問題的資料結構。本篇筆記會介紹其原理，也會說明此資料結構在題目上如何應用

Fenwick Tree 簡介

為什麼需要 Fenwick Tree?

給一個經典的問題: 「給定一個長度為

$n$ 的數列

$a_i$ (

$1\le i\le n$)，即

$q$ 比詢問，每筆詢問給定

$l,r$，求區間

$[l,r]$ 的總和」這個問題非常基本，定義一個前綴和陣列

$pr{e}_i=\sum _{j=1}^i{a}_j$，並預處理之，再使用差分

$pr{e}_r-pr{e}_{l-1}$，即可算出

$a_l+a_{l+1}+...+a_r$

Zerojudge e346. 區間和練習實作如下:

// 以上略
int n, q, l, r;
cin >> n;
vector<long long> a(n), pre(n + 1, 0);
for (int i = 0; i < n; i++) {
    cin >> a[i];
    pre[i + 1] = pre[i] + a[i];
}
cin >> q;
while (q--) {
    cin >> l >> r;
    cout << pre[r] - pre[l - 1] << '\n';
}

然而，當題目給的數列「可以在詢問過程中對任一個

$a_i$ 加值

$v$」，那麼前綴和陣列

$pr{e}_i$~

$pr{e}_n$ 都加值

$v$。在最差情況下，若都是對

$x_1$ 加值，那麼每次加值時間複雜度為

$O(n)$，而這種複雜度非常糟糕。因此我們需要一個好的資料結構來維護前綴和，使每次修改都可以在很小的時間內完成

原理說明

這段不知道也沒關係

查詢前綴和

給定一個長度為

$n$ 的數列

$a$，我們可以建構長度為

$n$ 的陣列

$pre$ ，代表

$pr{e}_i=\sum _{j=1}^i{a}_j$，其中

$1\le i\le n$。考慮將

$pre$ 以二進位的 index 拆分，並以

$s$ 表示。拆分方法是用二進位表示法以 index 最右邊的

$1$ 逐一刪去，並將每次刪去後的結果對應到的

$s_i$ 加總，直到

$i=0$ 停止。舉例像是

$pr{e}_{11}=s_{11}+s_{10}+s_8+s_0$

要完成此拆分，需要先建構陣列

$s$，如下表。其中 contents 是指

$a$ 的區間加總

index	0	1	2	3	4	5	6	7	8
contents	0	1	1~2	3	1~4	5	5~6	7	1~8

index	9	10	11	12	13	14	15	16
contents	9	9~10	11	9~12	13	13~14	15	1~16

我們可以定義一個函數

$lowbit(x)$ 代表

$x$ 在二進位表示中最右邊的

$1$ (即 least significant bit)。可以利用補數的特性來定義

$lowbit(x)=x\mathrm{\&}-x$

int lowbit(int x) { 
    return x & -x; 
}

如此一來，當我們想要詢問第

$k$ 項的前綴和時，就可以使用上述的演算法來完成查詢

int query(int x) {
    int pre = 0;               // 紀錄答案
    for (; x; x -= lowbit(x))  // 每次減去 least significant bit
        pre += s[x];           // 加上去
    return pre;
}

更新數值

在更新數值

$a_i$ 時，會發現

$pr{e}_i,pr{e}_{i+1},...,pr{e}_n$ 都會受影響。如上述所建構的

$s$，假設我們要使

$a_{11}$ 加值

$v$，我們可以觀察到會受影響的

$s$ 陣列數值有

$s_{11}$、

$s_{12}$ 與

$s_{16}$，這剛好會是

$i$ 不斷加上

$lowbit(i)$ 的結果 (

$11+lowbit(11)=12$、

$12+lowbit(12)=16$)。因此我們可以得到以下算法

void update(int i, ll v) {  // 將 i 的值加上 v
    for (; i < n; i += lowbit(i))
        s[i] += v;
}

以下面樹狀圖表示會更直覺一點。由於這是以二進制編號來做更新的資料結構，因此提出此想法的原作者將其命名為 Binary Indexed Tree

圖源: 海大競程 - 2025 離散化+BIT

建構資料結構

若想要將整個

$a$ 陣列塞入 BIT，可以將陣列

$s$ 先初始化為

$0$，再呼叫

$update()$ 函數去更新數值

要注意

$s$ 跟 1-based，而

$a$ 是 0-based

vector<int> s;
void construct(vector<int> a) {
    n = a.size();
    s.clear(), s.resize(n + 1, 0);
    for (int i = 1; i <= n; i++)
        update(i, a[i - 1]);
}

時間複雜度分析

查詢與更新均與樹高有關

• 查詢前綴和 :
  $O(logn)$
• 更新數值 :
  $O(logn)$
• 建構資料結構 :
  $O(nlogn)$

完整程式碼

變數名稱同上述所示，我們可以用 struct 包起來避免變數互相影響
注意有些變數在數字很大的時候可以用 long long 宣告

struct Fenwick {
    int n;
    vector<int> s;
    int lowbit(int x) { return x & -x; }
    Fenwick(int _n) {
        n = _n + 1;
        s.clear(), s.resize(n, 0);
    }
    void update(int i, int v) {  // 更新數值
        for (; i < n; i += lowbit(i))
            s[i] += v;
    }
    int query(int x) {  // 查詢前綴和
        int pre = 0;
        for (; x; x -= lowbit(x))
            pre += s[x];
        return pre;
    }
    Fenwick(vector<int> a) {           // 建構資料結構
        n = a.size();                  // a 是 0-based
        s.clear(), s.resize(n + 1, 0); // s 是 1-based
        for (int i = 1; i <= n; i++)
            update(i, a[i - 1]);
    }
};

經典例題說明

區間求和問題

題目

給定一個長度為

$n$ 的數列

$a_i$ (

$1\le i\le n$)，及

$q$ 比詢問，每筆詢問給定

$l,r$，求區間

$[l,r]$ 的總和

題解

查詢區間可以使用差分的技巧完成
剩下套模板即可

實作程式碼

int l, r, n, q;
long long a;
cin >> n; // 輸入陣列長度
Fenwick bit(n);

for (int i = 0; i < n; i++)
    cin >> a, bit.update(i + 1, a); // 輸入陣列, 更新 bit
cin >> q; // 輸入詢問數
while (q--) {
    cin >> l >> r; // 輸入區間
    cout << bit.query(r) - bit.query(l - 1) << '\n';
}

逆序數對問題

題目

給定一個長度為

$n$ 的數列

$a$。對於

$a$ 而言，若

$a_i>a_j$ 且

$1\le i<j\le n$，則稱

$(a_i,a_j)$ 為一組逆序數對。求數列

$a$ 中有多少組逆序數對

舉例假設一長度為

$5$ 的數列

$a=[4,1,3,2,5]$，則

$a$ 有

$4$ 組逆序數對，分別為:

$(4,1),(4,3),(4,2),(3,2)$

限制

$1\le n\le 2\times {10}^5$

$-{10}^9\le a_i\le {10}^9$, for all

$i$

題解

• 觀察一 : 最直觀的方式就是用

  $O(n^2)$ 去掃描整個陣列。若開兩個 for 迴圈由右往所掃，可以發現有些數字會重複被掃描到。i.g. 在找到
  $(3,2)$ 這組之後又會找到
  $(4,2)$，發現
  $2$ 被重新掃過。可以考慮將每個出現的數字出現次數記錄到一個陣列
  $cnt[]$ 之中

• 觀察二 : 若建立了用於計數的

  $cnt[]$，可以發現當我們掃描到新的數字
  $a_i$ 時，算出此時的前綴和
  $cnt[1]+cnt[2]+...+cnt[a_i-1]$，就可以知道「比
  $a_i$ 還小的數字數量」。由於是由右往左掃描，
  $a_i$ 位於其他數字左邊，符合
  $1\le i<j\le n$，又因前綴和只會加到比
  $a_i$ 小的數字的數量，所以也符合
  $a_i>a_j$。因此每次將「比
  $a_i$ 還小的數字數量」加總，就可以得到逆序數對數量

• 觀察三 : 前綴和的資料結構可以用 BIT 來實作，有效減少

  $cnt[]$ 單一數值修改的時間複雜度

實作程式碼

// 以上略
int n, ans = 0;
cin >> n; // 輸入長度
vector<int> a(n); // 0-based
for (int i = 0; i < n; i++) 
    cin >> a[i]; // 輸入陣列

Fenwick bit(mxn); // 開數字最大的 BIT
for (int i = n - 1; i >= 0; i--) {
    ans += bit.query(a[i] - 1);  // 找小於 a[i] 的數量
    bit.update(a[i], 1); // 更新數量
}
cout << ans << '\n'; // 輸出答案

此演算法的時間複雜度為:

$O(nlogn)$

離散化

以上實作之中，我們會以數字的大小來建立資料結構

$bit$。然而，若數值為

${10}^9$ 或是負值，則無法正常宣告

$bit$ 中的陣列

$s$，因此我們需要用離散化的技巧解決問題

離散化的實作非常簡短，步驟只有以下:

1. 將陣列
   $a$ 複製到陣列
   $tmp$
2. 排序陣列
   $tmp$
3. 找到重複的數並刪除，此時會得到一陣列
   $tmp$，可以看作是每個
   $tm{p}_j$ 貼上一個新編號
   $j$
4. 將陣列的每個數
   $a_i$ 用二分搜尋找到對應的
   $tm{p}_j$，並以
   $j$ 作為
   $a_i$ 的新值

// 這段程式碼是 0-based
vector<int> tmp(a);  // 將 a 複製到 tmp
sort(tmp.begin(), tmp.end()); // 將其排序
tmp.erase(unique(tmp.begin(), tmp.end()), tmp.end()); // 找到並刪除重複的數
for (int i = 0; i < n; i++) // 重新編號
  a[i] = lower_bound(tmp.begin(), tmp.end(), a[i]) - tmp.begin();

此演算法的時間複雜度為:

$O(nlogn)$

離散化的精華在於，陣列在保持了原本數值大小順序的情況下，縮小數值的值域，是個常見的解題技巧

二維偏序問題

題目

給定兩個長度為

$n$ 的陣列

$a,b$，問總共有幾組

$(i,j)$ 滿足

$a[i]\le a[j]$ 且

$b[i]\le b[j]$

限制

$1\le n\le 2\times {10}^5$

$0\le a_i,b_j\le {10}^9$

題解

可以將每個

$a_i$ 與

$b_i$ 看做數對

$(a_i,b_i)$，合起來就是一個數對陣列

$p=(first,second)$。為了滿足

$a[i]\le a[j]$，可以先將 數對陣列

$p$ 以

$first$ 做排序，如此一來就可以將問題轉化成對

$second$ 求反的逆序數對

程式碼實作

// 以上略
typedef pair<int, int> pii;
int n;
cin >> n;  // 輸入長度

vector<pii> p(n);
for (int i = 0; i < n; i++) {
    cin >> p[i].first >> p[i].second;
    p[i].first++, p[i].second++;  // 因為 BIT 是 1-based
}

sort(p.begin(), p.end(), [&](pii a, pii b) {
    if (a.first == b.first)
        return a.second < b.second;
    return a.first < b.first;
});  // 對 first 排序

Fenwick bit(n);   // 宣告 bit
int ans = 0;  // 紀錄答案

for (int i = 0; i < n; i++) {  // 求逆序數對
    ans += bit.query(p[i].second - 1);
    bit.update(p[i].second, 1);
}

cout << ans << '\n'; // 輸出答案

以上程式碼可以對

$second$ 進行離散化

題目練習

AtCoder Fenwick Tree (裸的)
CSES Range Update Queries (區間修改?)
Zerojudge b373. [福州19中]车厢重组 (逆序數對 or 窮舉)
ABC231 - F. Jealous Two (二維偏序)
Zerojudge a457. TOI2010 第五題：餐廳評鑑 (離散化 + 逆序數對)
Zerojudge d542. 10810 - Ultra-QuickSort (逆序數對)
CSES Sliding Window Median (二分搜 + BIT)
Zerojudge f315. 4. 低地距離 (計數)
Codeforces Round 261 D. Pashmak and Parmida's problem (計數)
Codeforces Beta Round 57 E. Enemy is weak (3-逆序數對)
LeetCode - 493. Reverse Pairs (2 倍逆序數對)
Zerojudge d799. 区间求和 (開兩個 BIT 或當線段樹毒瘤)

---

參考資料

海大競程 - 離散化+BIT
A New Data Structure for Cumulative Frequency Tables - peter m. fenwick
CP-Algorithms - Fenwick Tree
資訊之芽 - Fenwick tree
麗山演算法讀書會 - Fenwick(BIT, 樹狀數組)
wikipedia - Fenwick tree

---

ShanC 程式競賽筆記
作者: ShanC
更新: 2025/3/2