Fenwick Tree 用 15 行 code 做到線段樹 50 行才能做的事——前提是你只需要前綴和。
先講結論
Fenwick Tree（又叫 Binary Indexed Tree）利用二進位的巧妙性質，在 O(log n) 內完成前綴和查詢和單點更新。程式碼極短、常數極小、空間只要 O(n)。但它不支援區間最值——需要那個的話請用 Segment Tree。
lowbit：整個結構的核心
lowbit(x) = x & (-x)，取出 x 最低位的 1。
x = 6 → 二進位 110 → lowbit = 2 (10)
x = 12 → 二進位 1100 → lowbit = 4 (100)
x = 8 → 二進位 1000 → lowbit = 8 (1000)
這個小小的位元運算決定了每個節點管理多大的區間：tree[i] 管理 arr[i - lowbit(i) + 1 ... i]。
索引 1 (001), lowbit=1 → 管 [1,1]
索引 2 (010), lowbit=2 → 管 [1,2]
索引 3 (011), lowbit=1 → 管 [3,3]
索引 4 (100), lowbit=4 → 管 [1,4]
索引 6 (110), lowbit=2 → 管 [5,6]
索引 8 (1000), lowbit=8 → 管 [1,8]
看到規律了嗎？2 的冪次位置管更大的區間，奇數位置只管自己。
兩個操作，各 5 行
前綴和查詢：從 i 開始，每次減 lowbit，把經過的節點加起來。
int prefixSum(int i) {
int sum = 0;
while (i > 0) {
sum += tree[i];
i -= i & (-i); // 減 lowbit
}
return sum;
}比如查 prefixSum(7)：7(111) → 加 tree[7]，6(110) → 加 tree[6]，4(100) → 加 tree[4]，結束。三步搞定。
單點更新：從 i 開始，每次加 lowbit，沿路更新所有受影響的節點。
void update(int i, int delta) {
while (i <= n) {
tree[i] += delta;
i += i & (-i); // 加 lowbit
}
}更新 arr[3]：3(011) → 更新 tree[3]，4(100) → 更新 tree[4]，8(1000) → 更新 tree[8]。沿路往上。
區間和：就是兩個前綴和相減。
int rangeSum(int L, int R) {
return prefixSum(R) - prefixSum(L - 1);
}Fenwick Tree vs Segment Tree
| Fenwick Tree | Segment Tree | |
|---|---|---|
| 程式碼 | ~15 行 | ~50 行 |
| 空間 | O(n) | O(4n) |
| 常數 | 極小 | 較大 |
| 前綴和 | 原生支援 | 要查 [0, i] |
| 區間最值 | 不支援 | 支援 |
| 區間更新 | 需要差分技巧 | Lazy Propagation |
我的選擇標準：如果題目只涉及前綴和/區間和，無腦 Fenwick Tree。需要最值或複雜的區間操作才上線段樹。
2D 擴展
Fenwick Tree 可以很自然地擴展到二維矩陣的區域和查詢：
void update(int x, int y, int delta) {
for (int i = x; i <= n; i += i & (-i))
for (int j = y; j <= m; j += j & (-j))
tree[i][j] += delta;
}外層 loop 走 x 軸、內層走 y 軸，各自用 lowbit 跳。跟一維的邏輯完全一樣，只是多一層。
為什麼叫 Binary Indexed Tree？
因為所有操作都是在「索引的二進位表示」上做文章。加 lowbit 是往父節點走，減 lowbit 是往前一段區間走。整個結構隱含在二進位裡，不需要真的建一棵樹。
這是我覺得最精妙的資料結構設計之一——用最少的概念（一個位元運算）撐起最實用的功能。
Fenwick Tree 是那種「看懂了覺得太優雅、沒看懂覺得是黑魔法」的結構。lowbit 這個 trick 大概是演算法界最高的投資報酬率。