树状数组——快速统计和修改的魔法树

想象一下，你有100个小朋友的零花钱记录，老师常常要问：“前30个小朋友一共有多少钱？”而且还会经常修改某个小朋友的钱数。如果每次重新加一遍，要加30次，改一次又要重新算，非常慢。树状数组（也叫Fenwick树）就像一棵“魔法树”，它能用很少的步骤（大约 log₂100 ≈ 7次）算出结果，修改也只要7次。它利用二进制来组织数据，让求和与修改都变得飞快。

1. 树状数组是怎么“长”的？

树状数组的底层还是一个普通的数组，但下标从 1 开始（不是0）。数组的每个位置 bit[i] 并不只存第 i 个元素的值，而是存 一段连续区间 的和。这段区间有多长？由 i 的二进制表示中 最低位的1 来决定。

我们用一个神奇的函数 lowbit(x) 来找到这个“最低位的1”所代表的数值：

int lowbit(int x) {
    return x & -x;   // 负数的补码与原码按位与，只保留最低位的1
}

例如：

• lowbit(3)：3的二进制是 011，-3的补码是 101，按位与得 001，结果1。
• lowbit(4)：4的二进制是 100，-4的补码是 100，按位与得 100，结果4。
• lowbit(6)：6的二进制是 110，-6的补码是 010，按位与得 010，结果2。

含义：lowbit(i) 就是区间 [i - lowbit(i) + 1, i] 的长度。所以 bit[i] 存储的是从 i-lowbit(i)+1 到 i 这 lowbit(i) 个数的和。

比如 bit[4]（lowbit(4)=4）存的是区间 [1,4] 的和；bit[6]（lowbit(6)=2）存的是区间 [5,6] 的和。

这样，整个数组就像一棵隐形的树：每个节点覆盖一段区间，父节点由 i += lowbit(i) 得到，子节点由 i -= lowbit(i) 得到。修改一个点，顺着父节点一路向上更新；查询前缀和，顺着子节点一路向左累加。

2. 核心操作：单点修改和前缀查询

（1）给某个小朋友的零花钱加钱：add(idx, delta)

如果第 idx 个小朋友的零花钱增加了 delta，那么所有 包含 这个位置的区间都要更新。包含 idx 的区间对应的下标是：idx、idx + lowbit(idx)、idx + lowbit(idx) + lowbit(...) …… 直到超过数组大小 n。

void add(int idx, int delta) {
    while (idx <= n) {          // 不能超出范围
        bit[idx] += delta;      // 给覆盖区间加上delta
        idx += lowbit(idx);     // 跳到下一个包含它的区间
    }
}

比如 n=8，修改第3个位置：3→4→8（3+lowbit(3)=4，4+lowbit(4)=8）。所以 bit[3]、bit[4]、bit[8] 都要加。

（2）求前几个小朋友的总零花钱：sum(idx)

要求前 idx 个数的和，只需要把以 idx 结尾的所有区间累加起来。这些区间对应的下标是：idx、idx - lowbit(idx)、idx - lowbit(idx) - lowbit(...)…… 直到0。

int sum(int idx) {
    int res = 0;
    while (idx > 0) {
        res += bit[idx];        // 累加上这个区间的和
        idx -= lowbit(idx);     // 跳到上一个不重叠的区间
    }
    return res;
}

比如求前7个数的和：7→6→4→0（7-lowbit(7)=6，6-lowbit(6)=4，4-lowbit(4)=0）。累加 bit[7]、bit[6]、bit[4] 即可，正好覆盖了 [1,7]。

3. 生活中的例子：零花钱统计

小明记录了5个小朋友的零花钱（单位：元）：[1, 2, 3, 4, 5]（下标从1开始）。我们用树状数组初始化：

int arr[] = {0, 1, 2, 3, 4, 5};  // arr[0]留空，下标从1开始
n = 5;
for (int i = 1; i <= n; i++) add(i, arr[i]);

此时树状数组内部是：

• bit[1] = 1（区间[1,1]）
• bit[2] = 1+2 = 3（区间[1,2]）
• bit[3] = 3（区间[3,3]）
• bit[4] = 1+2+3+4 = 10（区间[1,4]）
• bit[5] = 5（区间[5,5]）

现在第3个小朋友又得到2元奖励，执行 add(3, 2)：

• 更新 bit[3] += 2 → 变成5
• 更新 bit[4] += 2 → 变成12
• 更新 bit[8]（超出n=5，停止）

然后老师问“前4个小朋友一共有多少钱？”执行 sum(4)：

• res += bit[4] = 12
• idx = 4 - lowbit(4) = 0，结束 → 结果12。

手动验算：原前4个和=1+2+3+4=10，第3个加了2后变成1+2+5+4=12，正确。

4. 新手容易犯的错误

• 下标从1开始，不是0：如果数组下标从0开始，lowbit(0)=0 会陷入死循环。通常我们定义 arr[0]=0，实际数据从1开始存。
• 忘记初始化：开始时树状数组 bit 全部为0，需要把所有元素通过 add 加进去，或者直接用原数组的每个值调用一次 add。
• 数组大小开不够：树状数组需要 n+5 的空间（因为下标到n）。如果查询或更新时 idx 超过n，会越界。
• 误用 sum(l,r) 求区间和：树状数组直接求的是前缀和。要求区间 [l, r] 的和，要用 sum(r) - sum(l-1)。
• 混淆 add 和 sum 的循环方向：add 是向上（加 lowbit），sum 是向下（减 lowbit）。记反会导致错误。

5. 完整可运行的代码（零花钱例子）

#include <iostream>
using namespace std;

const int N = 100010;
int bit[N], n;         // bit: 树状数组, n: 数据个数

int lowbit(int x) {
    return x & -x;     // 返回最低位的1代表的数值
}

void add(int idx, int delta) {
    while (idx <= n) {
        bit[idx] += delta;   // 给覆盖区间加delta
        idx += lowbit(idx);  // 跳到下一个包含idx的区间
    }
}

int sum(int idx) {
    int res = 0;
    while (idx > 0) {
        res += bit[idx];     // 累加当前区间和
        idx -= lowbit(idx);  // 跳到上一个不重叠的区间
    }
    return res;
}

int main() {
    n = 5;
    int arr[] = {0, 1, 2, 3, 4, 5}; // arr[0]不用，下标从1开始

    // 初始化树状数组
    for (int i = 1; i <= n; i++) {
        add(i, arr[i]);       // 把每个元素放入树状数组
    }

    cout << "初始前4个和: " << sum(4) << endl;   // 1+2+3+4=10

    add(3, 2);    // 第3个小朋友加了2元

    cout << "修改后前4个和: " << sum(4) << endl; // 1+2+5+4=12

    // 求区间 [2,5] 的和
    cout << "区间[2,5]的和: " << sum(5) - sum(1) << endl; // 2+5+4+5=16

    return 0;
}

输出：

初始前4个和: 10
修改后前4个和: 12
区间[2,5]的和: 16

6. 树状数组还能干什么？

除了单点修改、前缀查询，树状数组还有很多经典应用：

• 逆序对统计：从左到右扫描数组，每遇到一个数 x，先查询树状数组中大于 x 的个数（即 sum(n) - sum(x)），然后把 x 加入树状数组（add(x,1)）。所有结果累加就是逆序对数量。
• 区间加、区间求和（配合差分思想）：维护两个树状数组，可以实现区间加、区间求和，功能堪比线段树，但代码更短。
• 求第k小的数（权值树状数组）：在值域上建树状数组，每个位置存该值出现的次数，然后二分查找。

7. 相关知识点指引

• 前缀和与差分：树状数组是前缀和的高效动态版本，而差分数组可以快速实现区间加。两者结合就是“树状数组的区间加、区间求和”。
• 线段树：功能更强大（支持区间修改、区间查询多种操作），但代码更长、常数更大。如果只需要单点修改+区间求和，树状数组是首选。
• 二进制与位运算：理解 lowbit 需要懂二进制补码，这是树状数组的数学基础。
• 离散化：当值域很大时，需要把数值映射到1~m，再用树状数组处理（比如统计逆序对时）。

树状数组虽然小巧，但威力无穷。它就像一支魔法棒，让你在一分钟内解决原本要跑很久的求和问题。掌握了它，很多看似复杂的统计题目都会变得简单明了。