树状数组：从零开始理解这个“小而美”的数据结构
说实话，我第一次接触树状数组的时候，心里想的是：这玩意儿到底有什么用？
那时候我在做一个在线评测系统的排名模块，需要频繁更新选手分数，还要快速查询某个区间的总分。用普通数组吧，更新快但查询慢；用前缀和数组吧，查询快但更新慢。两头都不讨好。
后来一位老同事跟我说：“你试试树状数组。” 嗯，一试就回不去了。
树状数组是什么？
树状数组，英文叫 Fenwick Tree，也叫 Binary Indexed Tree（BIT）。它本质上是一个数组，但通过巧妙的索引设计，能同时支持快速的单点更新和区间查询。
说白了，它就是用一种“二进制思维”来管理数据。你想想看，计算机最擅长的就是二进制运算，树状数组正好利用了这一点。
核心思想：每个位置 i 存储的是原数组中某一段连续区间的和。这段区间的长度由 i 的二进制最低位 1 决定。
比如，位置 6（二进制 110），最低位 1 对应的是 2，所以它存储的是原数组第 5 到第 6 个元素的和。位置 8（二进制 1000），最低位 1 对应的是 8，所以它存储的是原数组第 1 到第 8 个元素的和。
这个“最低位 1”对应的值，有个专门的函数叫 lowbit：
int lowbit(int x) {
return x & (-x);
}我个人习惯把这个函数记成“取最后一个 1 的位置”。你试试看，6 & (-6) 等于 2，8 & (-8) 等于 8，没错吧？
树状数组的结构图
下面这张图展示了树状数组的存储结构。每个节点代表树状数组中的一个位置，它覆盖了原数组中的一段连续区间。
单点更新与区间查询
这是树状数组最经典的应用场景。我当年做排名系统用的就是这一套。
单点更新
假设我们要把 a[i] 加上一个值 val。普通数组直接改就行，但树状数组需要更新所有“覆盖了 i 这个位置”的 c[j]。
怎么找到这些 c[j]？很简单：从 i 开始，每次加上 lowbit(i)，直到超过 n。
void add(int i, int val) {
while (i <= n) {
c[i] += val;
i += lowbit(i);
}
}举个例子：更新 a[3]，需要更新 c[3]、c[4]、c[8]。因为 lowbit(3)=1，3+1=4；lowbit(4)=4，4+4=8；8 超过 n 就停。
小技巧：我刚开始学的时候，总记不住是加 lowbit 还是减 lowbit。后来我总结了一个口诀：更新往上走，查询往左走。更新时 i += lowbit(i)，查询时 i -= lowbit(i)。
区间查询
查询前缀和 [1..i] 也很直接：从 i 开始，每次减去 lowbit(i)，累加 c[i]。
int sum(int i) {
int res = 0;
while (i > 0) {
res += c[i];
i -= lowbit(i);
}
return res;
}要查询 [l..r] 的区间和，就用 sum(r) - sum(l-1)。
时间复杂度：单点更新 O(log n)，区间查询 O(log n)。
区间更新与单点查询
这个场景稍微绕一点，但也很实用。比如你要给数组的某个区间 [l..r] 统一加上一个值，然后查询某个位置的值。
怎么做？用差分思想。
我们维护一个差分数组 d，其中 d[i] = a[i] - a[i-1]。那么给 [l..r] 加上 val，等价于 d[l] += val，d[r+1] -= val。查询 a[i] 就是求 d[1..i] 的前缀和。
你看，这不就变成单点更新 + 区间查询了吗？只不过这次树状数组维护的是差分数组。
// 区间更新 [l..r] 加上 val
void range_add(int l, int r, int val) {
add(l, val);
add(r + 1, -val);
}
// 单点查询 a[i]
int point_query(int i) {
return sum(i);
}注意：这里 add 和 sum 函数跟前面一模一样，只是维护的对象变成了差分数组。我曾经在项目里搞混过，把差分数组当成原数组来更新，结果查出来的数据全乱了。嗯，调试了整整一个下午才找到问题。
树状数组与线段树的比较
很多初学者会问：有了线段树，为什么还要学树状数组？
我的回答是：杀鸡不用牛刀。
来看个对比表格：
| 特性 | 树状数组 | 线段树 |
|---|---|---|
| 代码量 | 极短（核心代码不到10行） | 较长（建树、更新、查询各需递归） |
| 时间复杂度 | O(log n) | O(log n) |
| 空间复杂度 | O(n) | O(4n) |
| 支持的操作 | 前缀和、单点更新、区间更新（需差分） | 区间和、区间最值、区间更新（懒标记） |
| 适用场景 | 求和类问题，操作简单 | 复杂区间操作，需要懒标记 |
| 常数因子 | 小（位运算，无递归） | 大（递归调用，函数开销） |
我个人习惯是：能用树状数组解决的问题，绝不用线段树。为什么？因为树状数组的代码太清爽了，调试起来也快。线段树写起来动辄几十行，一个递归边界写错就够你喝一壶的。
但话说回来，如果问题涉及区间最值、区间覆盖、或者需要同时维护多种信息，那还是老老实实用线段树吧。树状数组毕竟只擅长求和。
我的建议：面试或竞赛中，先判断问题是不是求和类。如果是，优先考虑树状数组。不是？再上线段树。这个顺序能帮你省下不少时间。
避坑指南
最后分享几个我踩过的坑：
- 数组下标从 1 开始：树状数组的下标必须从 1 开始，否则 lowbit(0)=0 会死循环。我刚开始写的时候习惯从 0 开始，结果程序直接卡死。
- 注意数据范围：树状数组的求和结果可能很大，记得用 long long。我曾经在排名系统里用 int 存总分，结果溢出变成负数，排名直接乱套。
- 初始化别偷懒：有些人喜欢用 memset 清零，但树状数组的初始化最好用循环逐个 add。因为 memset 是按字节赋值的，对 int 数组没问题，但对 long long 数组要小心。
- 区间更新别搞反：差分数组的更新是 d[l] += val, d[r+1] -= val，顺序别写反了。我犯过这个错，查了半天才发现是符号搞反了。
好了，树状数组的基本概念和操作就讲到这里。这东西看着简单，但用好了真的能解决很多实际问题。下次遇到需要频繁更新和查询的场景，不妨试试它。
公众号：蓝海资料掘金营，微信 deep3321