什么是树状数组
树状数组（Binary Indexed Tree / Fenwick Tree）用数组高效维护前缀和，支持单点更新与前缀查询，均为 O(log n)。相比线段树，它代码极短、常数极小，是”只做前缀操作”场景下的首选；代价是功能更弱（不好直接做区间最值、区间修改）。
核心思想：二进制分解
关键定义：lowbit(i) = i & (-i)，即 i 的二进制表示中最低位的 1 所代表的值。例如 lowbit(6) = lowbit(110₂) = 2。
树状数组 tree[i] 存储原数组区间 [i - lowbit(i) + 1, i] 的和。任何前缀 sum[1..x] 都可以被分解成 O(log n) 个不重叠的 tree 区间：
sum[1..x] = tree[x] + tree[x - lowbit(x)] + tree[x - lowbit(x) - lowbit(x - lowbit(x))] + ...
每次 x -= lowbit(x) 相当于把二进制中最低位的 1 抹掉，最多 log n 次就到 0，因此查询是 O(log n)。
正确性直观
- 更新：修改
a[x]后，要更新所有包含它的 tree 节点。从 x 开始不断x += lowbit(x)——每步是”二进制进位”，恰好跳到所有覆盖区间，例如更新 x=1 会影响 1, 2, 4, 8…，更新 x=6 影响 6, 8…； - 查询：
x -= lowbit(x)每次跳到下一个不重叠区间，保证前缀被完整、不重不漏地累加。
C++ 实现
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5e5 + 5;
int c[MAXN];
int n, m;
int lowbit(int x) { return x & -x; }
// 单点更新：a[pos] += value
void update(int pos, int value) {
while (pos <= n) {
c[pos] += value;
pos += lowbit(pos);
}
}
// 前缀和：sum[1..right]
int query(int right) {
int sum = 0;
while (right > 0) {
sum += c[right];
right -= lowbit(right);
}
return sum;
}
// 区间和：sum[left..right]
int rangeSum(int left, int right) {
return query(right) - query(left - 1);
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) {
int x; scanf("%d", &x);
update(i, x); // 构建：n 次 update，O(n log n)
}
while (m--) {
int op, a, b;
scanf("%d%d%d", &op, &a, &b);
if (op == 1) update(a, b); // 单点加
else printf("%dn", rangeSum(a, b)); // 区间和
}
return 0;
}
复杂度
- 单点更新 / 前缀查询：O(log n)；
- 初始化：n 次 update，O(n log n)（也可 O(n) 线性建树）；
- 空间：O(n)。
应用场景
- 动态前缀和：频繁”改一个数 + 查一段和”的题目，模板题（洛谷 P3374）即是；
- 逆序对计数：离散化后逐个插入统计，见《树状数组求逆序对》；
- 单点改 + 区间查的差分扩展：可推广到”区间改 + 单点查”（用差分数组），再配合另一棵 BIT 实现”区间改 + 区间查”；
- 需要求区间最值时不要用它——那是线段树/ST 表的领域。
