樹狀陣列
一：前言
樹狀陣列，也叫二叉索引樹（Binary Indexed Tree，簡稱 BIT），由 Peter M. Fenwick 於 1994 年發表。其初衷是解決資料壓縮裡累積頻率（Cumulative Frequency）的計算問題，現多用於動態地計算陣列的區間和。
二：單點更新，區間查詢
先看一個簡單的問題：有一個長度為 1000，初始為 0 的整型陣列，不妨設為 int a[1000] ，現對它有兩種操作，
delta
樹狀陣列的做法是，
#include <iostream>
using namespace std;
#define N 1000
int a[N];
int tree[N];
/* 除了最低位，清空其它所有為 1 的位 */
int LowBit(int x)
{
return x & (-x);
}
/* 元素 a[i] 的加 delta */
void Add(int i, int delta)
{
// 因為 tree[i] 正好可以覆蓋 a[i]，所以此句程式碼包括陣列 a[] 的宣告定義
// 皆可省略，加上它們只為讀者方便理解
a[i] += delta;
while (i <= N)
{
tree[i] += delta;
i += LowBit(i);
}
}
/* 求陣列 a[] 的前 i 項和 */
int Sum(int i)
{
int sum = 0;
while (i > 0)
{
sum += tree[i];
i -= LowBit(i);
}
return sum;
}
/* 求區間 a[i, j] 的和 */
int RangeSum(int i, int j)
{
return Sum(j) - Sum(i - 1);
}
int main()
{
memset(a, 0, sizeof(a));
memset(tree, 0, sizeof(tree));
Add(3, 2);
cout << RangeSum(1, 3) << endl; // 2
cout << RangeSum(2, 4) << endl; // 2
Add(10, 1);
cout << RangeSum(1, 3) << endl; // 2
cout << RangeSum(5, 12) << endl; // 1
cout << RangeSum(1, 11) << endl; // 3
return 0;
}
三：演算法分析
我們先給出上述程式碼中 tree[i] 的定義，
$$
tree[i]=\sum_{j=i-LowBit(i)+1}^i a[j] \tag{i ≥ 1}
$$
簡單點來說， tree[i] 表示陣列 a[] 中連續 LowBit(i) 個元素的和。我們配合上圖，舉幾個例子，
- 當 i = 2 時，
LowBit(2) = 2，則tree[2] = a[2] + a[1] - 當 i = 5 時，
LowBit(5) = 1，則tree[5] = a[5] - 當 i = 8 時，
LowBit(8) = 8，則tree[8] = a[8] +a[7] + ... + a[1] - 當 i = 12 時，
LowBit(12) = 4，則tree[12] = a[12] + a[11] + a[10] + a[9]
從圖中很容易看出，每一個 tree[i] 結點，都用一個頂部帶有灰色的矩形表示，而它的高度正好等於它所表示的範圍。由 tree[i] 的定義，我們可以很容易得出兩條性質，
性質一： Add() 中從任意位置 i（i > 0）往上進行更新（利用 i += LowBit(i) ），範圍可以覆蓋 a[i] 的所有 tree[] 結點都能得到更新。
性質二： Sum() 中從任意位置 i （i > 0）往下求和（利用 i -= LowBit(i) ），經過的所有的 tree[] 結點，它們所表示的區間範圍，都能恰好地銜接在一起（即區間既不會重疊，也不會斷開）。
現在我們假設這樣的場景：先對 a[i] 進行更新，即進行 Add(i, delta) 操作，那麼在向上更新所經過的 tree[] 結點，我們把它們標記為綠色，並用線依次連線；接下來求和 Sum(j) ，其中 0 < i < j，我們再把這時候向下經過的 tree[] 結點標記為橙色，也用線依次連線。
想一想，這兩條顏色不同的連結串列會是什麼樣子？
這就是性質三的內容，即下圖所示，
性質三： Add(i, delta) 和 Sum(j) 所經過的 tree[] 結點，有且僅有一個結點是相同的，其中 0 < i < j。
證明如下：
根據 0 < i < j，從二進位制角度，高位開始，找到第一個不同的位，
由於 i += LowBit(i) 和 j -= LowBit(j) ，所以它們一定會存在相等的情況。
對於唯一性的證明，用反證法即可。
假設存在兩個或兩個以上相同的結點，取其中最小的結點，我們發現，分別按照 i += LowBit(i) 和 j -= LowBit(j) 的更新規律，是無法得到其它較大的結點的，因此假設失敗，只會存在一個相同的結點。
四：區間更新，單點查詢
再來看一個經典的問題。
有一個長度為 1000，初始為 0 的整型陣列，不妨設為 int a[1000] ，現對它有兩種操作，
- 區間
[i, j]內的元素分別加上delta； - 求
a[i]的值。
如何用樹狀陣列來解決這個問題呢？
引入 a[] 的差分陣列，設其為 b[] ，即，
$$
\begin{align}
b[1] & = a[1] - a[0] \\
b[2] & = a[2] - a[1] \\
... \\
b[n] & = a[n] - a[n-1]
\end{align}
$$
我們來看看引入 b[] 的好處。
對於第一個操作：區間 [i, j] 內的元素分別加上 delta ，相當於 b[i] += delta; b[j + 1] -= delta 。
對於第二個操作：求 a[i] 的值，則相當於求和 $a[i] = b[i] + b[i-1] +...+b[1]$。
由此，我們定義 tree[i] ，
$$
tree[i]=\sum_{j=i-LowBit(i)+1}^i b[j] \tag{i ≥ 1}
$$
即陣列 b[] 中連續 LowBit(i) 個元素的和。
程式碼實現如下，
#include <iostream>
using namespace std;
#define N 1000
int tree[N];
/* 除了最低位，清空其它所有為 1 的位 */
int LowBit(int x)
{
return x & (-x);
}
/* a[i, N] 的值各加 delta，相當於 b[i] 加 delta */
void Add(int i, int delta)
{
while (i <= N)
{
tree[i] += delta;
i += LowBit(i);
}
}
/* a[i, j] 的值各加 delta，相當於 b[i] 加 delta，b[j + 1] 減 delta */
void RangeAdd(int i, int j, int delta)
{
Add(i, delta);
Add(j + 1, -delta);
}
/* 求 a[i] */
int Query(int i)
{
int sum = 0;
while (i > 0)
{
sum += tree[i];
i -= LowBit(i);
}
return sum;
}
int main()
{
memset(tree, 0, sizeof(tree));
RangeAdd(2, 5, 1);
cout << Query(1) << endl; // 0
cout << Query(3) << endl; // 1
cout << Query(6) << endl; // 0
RangeAdd(3, 8, 2);
cout << Query(2) << endl; // 1
cout << Query(4) << endl; // 3
cout << Query(10) << endl; // 0
return 0;
}