树状数组主要用来解决单点更新、区间查询的问题，特别是前缀和查询。它的代码实现非常短，效率也很高。
一、 问题背景：它解决了什么痛点？
想象一下你有一个数组 A，需要支持两种操作：
- 更新 (Update)：修改数组中某个元素
A[i]的值。 - 查询 (Query)：计算数组某个前缀
A[1] + A[2] + ... + A[i]的和。
我们来看看朴素的解法：
- 普通数组：更新 O(1)，查询 O(N)。每次查询都要遍历一遍，太慢。
- 前缀和数组：维护一个
sum数组，sum[i] = A[1] + ... + A[i]。查询 O(1)，但每次更新一个A[i]，需要更新sum[i]之后的所有元素，更新操作是 O(N)，也太慢。
树状数组提供了一个完美的折中方案：更新和查询操作都是 O(log N) 的复杂度。
二、 核心思想：lowbit 与二进制分解
树状数组的精髓在于它对数组下标的二进制表示的巧妙运用。它引入了一个核心函数 lowbit(x)。
lowbit(x)
- 定义：
lowbit(x)返回x的二进制表示中，最低位的 ‘1’ 以及它后面的所有 ‘0’ 构成的数值。 - 举例：
x = 6，二进制是110。最低位的 ‘1’ 在第二位，所以lowbit(6)是10（二进制），即十进制的2。x = 7，二进制是111。最低位的 ‘1’ 在第一位，所以lowbit(7)是1（二进制），即十进制的1。x = 8，二进制是1000。最低位的 ‘1’ 在第四位，所以lowbit(8)是1000（二进制），即十进制的8。
- 如何计算：有一个神奇的位运算技巧可以快速计算
lowbit。
为什么int lowbit(int x) { return x & -x; }x & -x有效？
在计算机中，负数通常用补码表示。-x的补码等于x的二进制按位取反再加一 (~x + 1)。这个操作会使得x最低位的 ‘1’ 以及它右边的所有位（原来是0）都保持不变，而这个 ‘1’ 左边的所有位都恰好与x相反。因此，x & (~x + 1)的结果就只保留了最低位的 ‘1’。
树状数组的结构
树状数组本身也是一个数组，我们称之为 tree 或 C。tree[x] 存储的不是 A[x] 的值，也不是 A[1]...A[x] 的和。
tree[x] 存储的是原始数组 A 在一个特定区间 (x - lowbit(x), x] 的和。
也就是说，tree[x] = A[x - lowbit(x) + 1] + ... + A[x]。这个区间的长度恰好是 lowbit(x)。
我们来看一个例子 (N=8):
tree[1]=A[1](区间长度lowbit(1)=1)tree[2]=A[1] + A[2](区间长度lowbit(2)=2)tree[3]=A[3](区间长度lowbit(3)=1)tree[4]=A[1] + A[2] + A[3] + A[4](区间长度lowbit(4)=4)tree[5]=A[5](区间长度lowbit(5)=1)tree[6]=A[5] + A[6](区间长度lowbit(6)=2)tree[7]=A[7](区间长度lowbit(7)=1)tree[8]=A[1] + ... + A[8](区间长度lowbit(8)=8)
可视化结构：
你可以把这种关系想象成一棵“树”。每个节点 x 的“父节点”是 x + lowbit(x)。
tree[8]
/
tree[4]
/ \
tree[2] tree[6]
/ \ / \
tree[1] tree[3] tree[5] tree[7]
三、 核心操作的实现
注意：树状数组的下标通常从 1 开始，以方便位运算。
1. 单点更新 add(x, delta)
- 目的：给原始数组的
A[x]增加一个值delta。 - 思路：当
A[x]改变时，我们需要更新所有管辖范围包含了A[x]的tree节点。 - 如何找到这些节点？ 从
x开始，不断地执行x = x + lowbit(x)，直到x超出数组范围。这个路径就是从x向上走到“树”的根的过程。 - 代码实现：
// 在位置 x 增加 delta void add(int x, int delta) { for (int i = x; i <= N; i += lowbit(i)) { tree[i] += delta; } }
2. 前缀和查询 query(x)
- 目的：计算
A[1] + ... + A[x]的和。 - 思路：这个和可以通过加总几个特定的
tree节点得到。例如，查询query(7):sum(1...7)=(A[1]...A[4])+(A[5]...A[6])+A[7]- 这恰好等于
tree[4] + tree[6] + tree[7]
- 如何找到这些节点？ 从
x开始，不断地执行x = x - lowbit(x)，直到x变为 0。这个路径就是把区间[1, x]分解成多个小块的过程。 - 代码实现：
// 查询前缀和 [1, x] int query(int x) { int sum = 0; for (int i = x; i > 0; i -= lowbit(i)) { sum += tree[i]; } return sum; }
四、 完整代码模板及示例
#include <iostream>
#include <vector>
const int MAXN = 100005;
int N; // 数组的大小
long long tree[MAXN]; // 树状数组，使用 long long 防止溢出
// lowbit 函数
int lowbit(int x) {
return x & -x;
}
// 单点更新：在位置 x 增加 delta
void add(int x, int delta) {
for (int i = x; i <= N; i += lowbit(i)) {
tree[i] += delta;
}
}
// 前缀和查询：查询 [1, x] 的和
long long query(int x) {
long long sum = 0;
for (int i = x; i > 0; i -= lowbit(i)) {
sum += tree[i];
}
return sum;
}
// 查询区间 [l, r] 的和
long long range_query(int l, int r) {
return query(r) - query(l - 1);
}
int main() {
// 假设数组大小为 8
N = 8;
int a[] = {0, 1, 3, 5, 7, 9, 11, 13, 15}; // a[0] 不用，从 a[1] 开始
// 初始化树状数组
for (int i = 1; i <= N; ++i) {
add(i, a[i]);
}
// 查询前缀和
std::cout << "Sum of [1, 3]: " << query(3) << std::endl; // 1+3+5 = 9
std::cout << "Sum of [1, 7]: " << query(7) << std::endl; // 1+3+5+7+9+11+13 = 49
// 查询区间和
std::cout << "Sum of [3, 6]: " << range_query(3, 6) << std::endl; // 5+7+9+11 = 32
// 单点更新：将 a[3] 的值从 5 增加到 8 (delta = 3)
std::cout << "\nUpdating a[3] by +3...\n";
add(3, 3);
// 再次查询
std::cout << "New sum of [1, 3]: " << query(3) << std::endl; // 1+3+(5+3) = 12
std::cout << "New sum of [3, 6]: " << range_query(3, 6) << std::endl; // (5+3)+7+9+11 = 35
return 0;
}
五、 总结与应用
优点：
- 效率高：更新和查询都是 O(log N)。
- 代码简短：易于实现，不易出错。
- 空间开销小：只需要一个和原数组等大的辅助数组。
局限：
- 只能处理满足结合律且有逆元的操作（如加减法、异或）。求区间最大/最小值这种操作无法直接用标准树状数组解决（需要特殊改造）。
- 功能相对线段树较少，例如复杂的区间更新操作难以实现。
常见应用：
- 单点修改，区间求和：最经典的应用。
- 区间修改，单点查询：通过维护一个差分数组，将区间修改转化为两次单点修改，单点查询转化为一次前缀和查询。
- 求逆序对：在归并排序或离散化后配合树状数组是经典解法。
- 二维树状数组：解决二维平面上的单点修改和矩形区域查询问题。