树状数组（Binary Indexed Tree）—— 优雅的前缀和利器

它能做什么？

树状数组（Fenwick Tree）在 $O(\log n)$ 时间内支持：

• 单点修改：add(i, x) — 位置 i 加上 x
• 前缀查询：sum(i) — 查询 $[1, i]$ 的区间和

区间和 $[l, r] = sum(r) - sum(l-1)$，一次减法搞定。

相比线段树：代码短、常数小；代价是只支持可逆操作（加法、异或等），不支持区间最值。

核心思想：lowbit

树状数组的基石是 lowbit —— 取一个数二进制最低位的 1：

lowbit(x) = x & -x

lowbit 的几何直觉

每个下标管辖一段区间，长度 = lowbit(i)：

下标:   1   2   3   4   5   6   7   8
       [1] [ ] [3] [ ] [5] [ ] [7] [ ]
       [1---2]               
       [1-----------4]
       [1---------------------------8]

• tree[1] 管 $[1, 1]$（长度 $lowbit(1)=1$）
• tree[2] 管 $[1, 2]$（长度 $lowbit(2)=2$）
• tree[3] 管 $[3, 3]$（长度 $lowbit(3)=1$）
• tree[4] 管 $[1, 4]$（长度 $lowbit(4)=4$）
• tree[8] 管 $[1, 8]$（长度 $lowbit(8)=8$）

树形结构

                   8
           ┌───────┴───────┐
           4              12
       ┌───┴───┐       ┌───┴───┐
       2       6      10      14
     ┌─┴─┐   ┌─┴─┐   ┌─┴─┐   ┌─┴─┐
     1   3   5   7   9  11  13  15

i 的父亲 = i + lowbit(i)，这正是 add 向上更新的路径。

add 函数：向上更新

修改位置 i，然后一路跳到父亲，直到超出范围。

i → i + lowbit(i) → i + lowbit(i) + lowbit(...) → ...

// 位置 i 加上 x（1‑based）
void add(int i, int x) {
    while (i <= n) {
        tree[i] += x;
        i += lowbit(i);   // 跳到父亲
    }
}

图示：add(3, x)

tree[3] += x  →  i = 3 + lowbit(3) = 4
tree[4] += x  →  i = 4 + lowbit(4) = 8
tree[8] += x  →  i = 8 + lowbit(8) = 16 > n，停止

                    [8] ← +x
           ┌─────────┘
          [4] ← +x
     ┌─────┘
    (3) ← +x  ← 起点

sum 函数：向下累加

从位置 i 开始，一路减去 lowbit，累加经过的节点。

i → i - lowbit(i) → i - lowbit(i) - lowbit(...) → ... → 0

// 查询 [1, i] 的前缀和
int sum(int i) {
    int res = 0;
    while (i > 0) {
        res += tree[i];
        i -= lowbit(i);   // 跳到前一段
    }
    return res;
}

图示：sum(7)

         tree[7] 管 [7,7]  →  i = 7 - lowbit(7) = 6
       + tree[6] 管 [5,6]  →  i = 6 - lowbit(6) = 4
       + tree[4] 管 [1,4]  →  i = 4 - lowbit(4) = 0，停止

[1,4]         [5,6]  [7,7]
  tree[4]     tree[6] tree[7]
  ← 加        ← 加     ← 起点

恰好不重不漏地覆盖了 $[1, 7]$。

用 add 构建树状数组

建树不需要特殊技巧，对每个元素调 add 就行。

vector<int> tree(n + 1);

void build(vector<int>& a) {
    for (int i = 0; i < a.size(); i++)
        add(i + 1, a[i]);   // 树状数组下标从 1 开始
}

复杂度：$O(n \log n)$，每个元素调一次 add。

优化：$O(n)$ 建树

void buildLinear(vector<int>& a) {
    for (int i = 1; i <= n; i++) {
        tree[i] += a[i - 1];               // 先加上自己
        int p = i + lowbit(i);
        if (p <= n) tree[p] += tree[i];     // 直接贡献给父亲
    }
}

本质上就是前缀和分块：每个节点直接把它管的那段和贡献到父亲，一轮扫完。

完整代码

class BIT {
    vector<int> tree;
    int n;

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

public:
    BIT(int size) : n(size), tree(size + 1) {}

    // 用 add 构建
    void build(vector<int>& a) {
        for (int i = 0; i < a.size(); i++)
            add(i + 1, a[i]);
    }

    // 位置 i 加上 x
    void add(int i, int x) {
        while (i <= n) {
            tree[i] += x;
            i += lowbit(i);
        }
    }

    // 查询 [1, i] 前缀和
    int sum(int i) {
        int res = 0;
        while (i > 0) {
            res += tree[i];
            i -= lowbit(i);
        }
        return res;
    }

    // 查询 [l, r] 区间和
    int rangeSum(int l, int r) {
        return sum(r) - sum(l - 1);
    }
};

手推一遍

以 a = [3, 1, 4, 1, 5, 9] 为例：

建树过程：

add(1, 3):  tree[1]+=3, tree[2]+=3, tree[4]+=3, tree[8]+=3
add(2, 1):  tree[2]+=1, tree[4]+=1, tree[8]+=1
add(3, 4):  tree[3]+=4, tree[4]+=4, tree[8]+=4
add(4, 1):  tree[4]+=1, tree[8]+=1
add(5, 5):  tree[5]+=5, tree[6]+=5, tree[8]+=5
add(6, 9):  tree[6]+=9, tree[8]+=9

最终 tree 数组：

i:       1   2   3   4   5   6   7   8
tree:    3   4   4   9   5  14   0  23
管辖:  [1] [1,2] [3] [1-4] [5] [5,6] [7] [1-8]

查询 sum(6)：

i=6: tree[6]=14 (管辖 [5,6])
i=4: tree[4]=9  (管辖 [1,4])
i=0: 停止
sum = 14 + 9 = 23
验证: a[1]+...+a[6] = 3+1+4+1+5+9 = 23 ✓

查询 rangeSum(2, 5)：

sum(5) = tree[5] + tree[4] = 5 + 9 = 14  (3+1+4+1+5)
sum(1) = tree[1] = 3                     (3)
rangeSum = 14 - 3 = 11
验证: a[2]+a[3]+a[4]+a[5] = 1+4+1+5 = 11 ✓

add 和 sum 的对称性

add:  i → i + lowbit(i)  → ...   (向上传播修改)
sum:  i → i - lowbit(i)  → ...   (向下收集贡献)

add 是在贡献数据，sum 是在收割数据。
两者互逆，走的恰好是同一棵树的不同方向。

复杂度

总结

1. lowbit 是灵魂 —— x & -x 管多宽、父亲是谁，全看它
2. add 向上跳：i += lowbit(i)，通知所有管辖者
3. sum 向下跳：i -= lowbit(i)，收集所有贡献者
4. 建树用 add：一行 add(i, a[i])，直观不出错

线段树能做的区间修改，树状数组加差分也能做；但"单点改、前缀查"永远是树状数组最舒适的场景。