5.1 节的前缀和查询飞快，但只要改一个数就要整个重算——树状数组用一个巧妙的二进制技巧，让"改一个数"和"查一段和"都只需要 O(log n)。
5.1 节讲过的前缀和数组，能在 O(1) 时间内查询任意区间的和——但它有一个致命短板：如果原数组中间的某个值被修改了，这个位置之后的所有前缀和都要跟着变，重新计算一遍就是 O(n)。如果题目要求"频繁修改单个值 + 频繁查询区间和"交替进行，前缀和数组就不够用了。
树状数组（Binary Indexed Tree，简称 BIT，也叫 Fenwick Tree）就是为了同时兼顾这两种操作而设计的：单点修改和前缀和查询，都只需要 O(log n)。
树状数组的核心是一个叫 lowbit 的运算：lowbit(x) = x & (-x)，取出 x 的二进制表示中最低位的 1 所代表的数值（比如 x=6，二进制是 110，最低位的 1 在第 2 位，lowbit(6)=2）。
树状数组用一个数组 tree[] 存储信息，但 tree[i] 存的不是 a[i] 本身，而是"原数组里一段区间的和"——具体管辖的是区间 (i - lowbit(i), i]（从 i - lowbit(i) + 1 到 i）。不同的 i，管辖的区间长度不同，恰好由 lowbit(i) 决定。
原数组 a = [3, 2, 5, 6, 1, 4, 7, 2]（下标从 1 开始，n=8）：
lowbit(i) 决定了每个 tree[i] 管辖区间的长度：lowbit(8)=8，所以 tree[8] 管辖了最大的一段 [1,8]；lowbit(1)=lowbit(3)=lowbit(5)=lowbit(7)=1，这些位置各自只管辖自己这一个数。这种"有的管一大段、有的只管一个点"的结构，用不多的空间（仍然只是一个长度为 n 的数组）就能同时支持快速修改和快速查询。把 a[3] 增加 2（从 5 变成 7）：需要更新所有管辖范围包含下标 3 的 tree[i]。做法是从 i=3 开始，不断执行 i += lowbit(i)，跳到下一个需要更新的位置，直到 i 超过 n：
| 当前 i | lowbit(i) | 更新 tree[i] | 跳到 i += lowbit(i) |
|---|---|---|---|
| 3 | 1 | tree[3]：5 → 7 | 3+1=4 |
| 4 | 4 | tree[4]：16 → 18 | 4+4=8 |
| 8 | 8 | tree[8]：30 → 32 | 8+8=16 > n=8，停止 |
i += lowbit(i)？只有"管辖区间包含下标 3"的 tree[i] 才需要更新——观察 ③ 的图会发现，这些 i（3、4、8）在树状数组的结构里，从下标 3 开始不断"跳到管辖范围更大、且仍然包含 3"的下一个位置，正好对应 i += lowbit(i) 这个操作。整个跳跃路径最多经过 O(log n) 个位置。查询 a[1]+a[2]+...+a[6]（前 6 个数的和）：从 i=6 开始，不断把 tree[i] 累加进答案，然后执行 i -= lowbit(i)，直到 i 变成 0：
| 当前 i | lowbit(i) | 累加 tree[i] | 累计和 | 跳到 i -= lowbit(i) |
|---|---|---|---|---|
| 6 | 2 | tree[6] = 5 | 5 | 6-2=4 |
| 4 | 4 | tree[4] = 16 | 21 | 4-4=0，停止 |
a[1]+...+a[6] = 3+2+5+6+1+4 = 21，和查询结果一致。刚才 ④ 把 a[3] 改成了 7（增加了 2），如果这时候重新查询 Query(6)，走的路径是 i=6→tree[6]=5，i=4→tree[4]=18（已经被 ④ 更新过），总和 5+18=23，正好是 21+2——修改的效果被正确地反映到了查询结果里。| 1 | int tree[MAXN], n; |
| 2 | |
| 3 | int Lowbit(int x) { return x & (-x); } // 取出 x 最低位的 1 |
| 4 | |
| 5 | void Update(int i, int delta) // 把 a[i] 增加 delta |
| 6 | { |
| 7 | for (; i <= n; i += Lowbit(i)) // ★ 往上跳，更新所有管辖范围包含 i 的位置 |
| 8 | tree[i] += delta; |
| 9 | } |
| 10 | |
| 11 | int Query(int i) // 查询 a[1] + a[2] + ... + a[i] |
| 12 | { |
| 13 | int sum = 0; |
| 14 | for (; i > 0; i -= Lowbit(i)) // ★ 往下跳，累加沿途的 tree[i] |
| 15 | sum += tree[i]; |
| 16 | return sum; |
| 17 | } |
| 18 | |
| 19 | int RangeSum(int l, int r) // 查询区间 [l, r] 的和 |
| 20 | { |
| 21 | return Query(r) - Query(l - 1); // 和 5.1 节前缀和求区间和的思路完全一样 |
| 22 | } |
[l, r] 的和，用两次前缀和相减：这一点和 5.1 节的前缀和数组是同一个思路——Query(r) - Query(l-1) 就是区间 [l,r] 的和。区别只在于：普通前缀和数组改一次要 O(n)，而这里的 Query 和 Update 都只要 O(log n)。lowbit(0) = 0，如果 Update 或 Query 传入下标 0，循环条件 i += Lowbit(i)（或 i -= Lowbit(i)）会永远停在 0，变成死循环。树状数组的下标约定统一从 1 开始，这也是 16.1 节离散化时特意 +1 让排名从 1 开始的原因。Update(i, delta) 里的 delta 是"变化量"（增加多少），不是"新值本身"。如果想把 a[i] 直接改成某个新值 x，需要先算出 delta = x - a[i]（旧值和新值的差），再调用 Update(i, delta)，同时记得更新记录旧值的数组。n，如果原始数据值域很大（比如坐标可以是 10⁹），必须先离散化压缩到 1~n，再用离散化后的排名当树状数组的下标，否则数组根本开不下。