# Fenwick Tree
Fenwick Tree 又稱 Binary Indexed Tree(樹狀數組)，以下簡稱 BIT，是一個方便解決區間與前綴和問題的資料結構。本篇筆記會介紹其原理，也會說明此資料結構在題目上如何應用
## Fenwick Tree 簡介
### 為什麼需要 Fenwick Tree?
給一個[經典的問題](https://zerojudge.tw/ShowProblem?problemid=e346): 「給定一個長度為 $n$ 的數列 $a_i$ ($1\leq i \leq n$)，即 $q$ 比詢問，每筆詢問給定 $l, r$，求區間 $[l, ~r]$ 的總和」這個問題非常基本，定義一個前綴和陣列 $pre_i=\sum_{j=1}^i a_j$，並預處理之，再使用差分 $pre_r - pre_{l - 1}$，即可算出 $a_l + a_{l+1} + ... +a_r$
[Zerojudge e346. 區間和練習](https://zerojudge.tw/ShowProblem?problemid=e346)實作如下:
```cpp
// 以上略
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$」，那麼前綴和陣列 $pre_i$~$pre_n$ 都加值 $v$。在最差情況下，若都是對 $x_1$ 加值，那麼每次加值時間複雜度為 $O(n)$，而這種複雜度非常糟糕。因此我們需要一個好的資料結構來維護前綴和，使每次修改都可以在很小的時間內完成
### 原理說明
||~~這段不知道也沒關係~~||
#### 查詢前綴和
給定一個長度為 $n$ 的數列 $a$，我們可以建構長度為 $n$ 的陣列 $pre$ ，代表 $pre_i=\sum_{j=1}^i a_j$，其中 $1\leq i\leq n$。考慮將 $pre$ 以二進位的 index 拆分，並以 $s$ 表示。拆分方法是用二進位表示法以 index 最右邊的 $1$ 逐一刪去，並將每次刪去後的結果對應到的 $s_i$ 加總，直到 $i = 0$ 停止。舉例像是 $pre_{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 ~\& ~-x$
```cpp
int lowbit(int x) {
return x & -x;
}
```
如此一來，當我們想要詢問第 $k$ 項的前綴和時，就可以使用上述的演算法來完成查詢
```cpp
int query(int x) {
int pre = 0; // 紀錄答案
for (; x; x -= lowbit(x)) // 每次減去 least significant bit
pre += s[x]; // 加上去
return pre;
}
```
#### 更新數值
在更新數值 $a_i$ 時，會發現 $pre_i, pre_{i+1},...,pre_{n}$ 都會受影響。如上述所建構的 $s$，假設我們要使 $a_{11}$ 加值 $v$，我們可以觀察到會受影響的 $s$ 陣列數值有 $s_{11}$、$s_{12}$ 與 $s_{16}$，這剛好會是 $i$ 不斷加上 $lowbit(i)$ 的結果 ($11 + lowbit(11)=12$、$12 + lowbit(12) = 16$)。因此我們可以得到以下算法
```cpp
void update(int i, ll v) { // 將 i 的值加上 v
for (; i < n; i += lowbit(i))
s[i] += v;
}
```
以下面樹狀圖表示會更直覺一點。由於這是以二進制編號來做更新的資料結構，因此提出此想法的原作者將其命名為 Binary Indexed Tree
<img src="https://hackmd.io/_uploads/SJnMXQLt6.png" style="margin: 0 auto; display: block; width: 400px">
<p class="text-center">
圖源: 海大競程 - 2025 離散化+BIT
</p>
#### 建構資料結構
若想要將整個 $a$ 陣列塞入 BIT，可以將陣列 $s$ 先初始化為 $0$，再呼叫 $update()$ 函數去更新數值
**要注意 $s$ 跟 1-based，而 $a$ 是 0-based**
```cpp
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(log ~n)$
- 更新數值 : $O(log ~n)$
- 建構資料結構 : $O(n~log~n)$
## 完整程式碼
變數名稱同上述所示，我們可以用 `struct` 包起來避免變數互相影響
注意有些變數在數字很大的時候可以用 `long long` 宣告
```cpp
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\leq i \leq n$)，及 $q$ 比詢問，每筆詢問給定 $l, r$，求區間 $[l, ~r]$ 的總和
#### 題解
查詢區間可以使用差分的技巧完成
剩下套模板即可
#### 實作程式碼
```cpp
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\leq i < j\leq n$，則稱 $(a_i, a_j)$ 為一組逆序數對。求數列 $a$ 中有多少組逆序數對
舉例假設一長度為 $5$ 的數列 $a = [4, 1, 3, 2, 5]$，則 $a$ 有 $4$ 組逆序數對，分別為: $(4,1), (4,3), (4,2), (3,2)$
#### 限制
$1 \leq n\leq 2\times 10^5$
$-10^9\leq a_i\leq 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\leq i < j\leq n$，又因前綴和只會加到比 $a_i$ 小的數字的數量，所以也符合 $a_i > a_j$。因此每次將「比 $a_i$ 還小的數字數量」加總，就可以得到逆序數對數量
- 觀察三 : 前綴和的資料結構可以用 BIT 來實作，有效減少 $cnt[~]$ 單一數值修改的時間複雜度
#### 實作程式碼
```cpp
// 以上略
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(n~log~n)$
#### 離散化
以上實作之中，我們會以數字的大小來建立資料結構 $bit$。然而，若數值為 $10^9$ 或是負值，則無法正常宣告 $bit$ 中的陣列 $s$，因此我們需要用**離散化**的技巧解決問題
離散化的實作非常簡短，步驟只有以下:
1. 將陣列 $a$ 複製到陣列 $tmp$
2. 排序陣列 $tmp$
3. 找到重複的數並刪除，此時會得到一陣列 $tmp$，可以看作是每個 $tmp_j$ 貼上一個新編號 $j$
4. 將陣列的每個數 $a_i$ 用二分搜尋找到對應的 $tmp_j$，並以 $j$ 作為 $a_i$ 的新值
```cpp
// 這段程式碼是 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(n~log~n)$
離散化的精華在於，陣列在保持了原本數值大小順序的情況下，縮小數值的值域，是個常見的解題技巧
### 二維偏序問題
#### 題目
給定兩個長度為 $n$ 的陣列 $a, b$，問總共有幾組 $(i, j)$ 滿足 $a[i] \leq a[j]$ 且 $b[i] \leq b[j]$
#### 限制
$1\leq n\leq 2\times 10^5$
$0\leq a_i, b_j\leq 10^9$
#### 題解
可以將每個 $a_i$ 與 $b_i$ 看做數對 $(a_i, b_i)$，合起來就是一個數對陣列 $p = (first, second)$。為了滿足 $a[i] \leq a[j]$，可以先將 數對陣列 $p$ 以 $first$ 做排序，如此一來就可以將問題轉化成對 $second$ 求反的逆序數對
#### 程式碼實作
```cpp
// 以上略
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](https://atcoder.jp/contests/practice2/tasks/practice2_b?lang=en) (裸的)
[CSES Range Update Queries](https://cses.fi/problemset/task/1651) (區間修改?)
[Zerojudge b373. [福州19中]车厢重组](https://zerojudge.tw/ShowProblem?problemid=b373) (逆序數對 or 窮舉)
[ABC231 - F. Jealous Two](https://atcoder.jp/contests/abc231/tasks/abc231_f) (二維偏序)
[Zerojudge a457. TOI2010 第五題：餐廳評鑑](https://zerojudge.tw/ShowProblem?problemid=a457) (離散化 + 逆序數對)
[Zerojudge d542. 10810 - Ultra-QuickSort](https://zerojudge.tw/ShowProblem?problemid=d542) (逆序數對)
[CSES Sliding Window Median](https://cses.fi/problemset/task/1076) (二分搜 + BIT)
[Zerojudge f315. 4. 低地距離](https://zerojudge.tw/ShowProblem?problemid=f315) (計數)
[Codeforces Round 261 D. Pashmak and Parmida's problem](https://mirror.codeforces.com/contest/459/problem/D) (計數)
[Codeforces Beta Round 57 E. Enemy is weak](https://codeforces.com/problemset/problem/61/E) (3-逆序數對)
[LeetCode - 493. Reverse Pairs](https://leetcode.com/problems/reverse-pairs/description/) (2 倍逆序數對)
[Zerojudge d799. 区间求和](https://zerojudge.tw/ShowProblem?problemid=d799) (開兩個 BIT 或當線段樹毒瘤)
----
## 參考資料
[海大競程 - 離散化+BIT](https://hackmd.io/@LeeShoWhaodian/2025-BIT#/)
[A New Data Structure for Cumulative Frequency Tables - peter m. fenwick](https://blogs.asarkar.com/assets/docs/algorithms/Fenwick%20Tree%20-%20Fenwick.pdf)
[CP-Algorithms - Fenwick Tree](https://cp-algorithms.com/data_structures/fenwick.html)
[資訊之芽 - Fenwick tree](https://www.csie.ntu.edu.tw/~sprout/algo2021/homework/hand10.pdf)
[麗山演算法讀書會 - Fenwick(BIT, 樹狀數組)](https://hackmd.io/@Lssh-Algorithm/r1n4upLDO)
[wikipedia - Fenwick tree](https://en.wikipedia.org/wiki/Fenwick_tree)
----
> [ShanC 程式競賽筆記](https://hackmd.io/@ShanC/B1ouGxqcC)
> 作者: ShanC
> 更新: 2025/3/2
Sign in with Wallet
Connect another wallet