树状数组（Binary Indexed Tree，又称 Fenwick Tree）是一种轻量级的区间数据结构，常用于单点更新和前缀和查询。它能把一次更新或一次查询从 O(n) 降到 O(log n)，而且代码量只有十来行，非常适合在算法题、实时排行榜、逆序对统计、动态第 K 小等场景中使用。很多初学者记住i += i & -i和i -= i & -i两个式子，却不明白它们背后的二进制语义，导致遇到区间修改、离散化、树状数组上二分时又容易写错。这篇文章从二进制索引的原理讲起，先带你跑通基础单点更新和前缀查询，再逐步扩展到逆序对、离散化、树状数组上的二分，最后给出常见错误排查路径和工程化建议。学完后，你能独立实现树状数组的常见应用，也能在遇到下标越界、查询结果不符、更新不生效等问题时快速定位根因。
1. 理解树状数组：从区间求和到二进制索引
1.1 为什么需要树状数组
先看一个经典问题。给定一个长度为 n 的整数数组 a，需要支持两种操作：
- 单点更新：把 a[i] 的值增加 delta。
- 前缀查询：求 a[1] + a[2] + ... + a[i] 的和。
如果直接用普通数组，单点更新很快，O(1) 就能完成；但前缀查询需要循环相加，最坏是 O(n)。如果预处理前缀和数组 prefix[i]，前缀查询可以做到 O(1)，但单点更新后需要重新计算受影响的所有前缀和，最坏也是 O(n)。当 n 很大、操作次数很多时，这两种做法都无法接受。
线段树也能解决这个问题，它能把单点更新和区间查询都做到 O(log n)。但线段树的实现需要建树、递归或者使用数组模拟二叉树，结构更重，代码更长，常数因子也更大。树状数组正是针对“单点更新 + 前缀查询”这类问题设计的轻量级结构。它同样能实现 O(log n) 的更新和查询，但空间占用只有 O(n)，代码结构非常紧凑。
树状数组的适用范围比线段树窄一些，但它覆盖了算法题里相当多的需求：前缀和、逆序对、区间和、动态第 K 小、差分维护区间修改等。理解树状数组的价值，不只是背模板，更是理解它如何利用整数二进制的位数来组织信息。
1.2 核心思想：二进制索引与 lowbit
树状数组的底层依赖一个关键函数 lowbit。对于正整数 x，lowbit(x)表示 x 的二进制表示中最低位的 1 所对应的值。例如：
- x = 6，二进制是 110，最低位的 1 在第二位，对应值 2，所以 lowbit(6) = 2。
- x = 8，二进制是 1000，最低位的 1 在最高位，对应值 8，所以 lowbit(8) = 8。
- x = 3，二进制是 11，最低位的 1 对应值 1，所以 lowbit(3) = 1。
计算 lowbit 的常用公式是x & -x。这是因为负整数在计算机中使用补码表示，-x等于把 x 按位取反再加 1，这样x & -x恰好能保留 x 最低位的 1。
树状数组用一个额外数组 c 来保存某些区间和。下标从 1 开始，c[i] 保存的是原数组中区间 [i - lowbit(i) + 1, i] 的和。也就是说，c[i] 所覆盖的区间长度恰好是 lowbit(i)。看一个 n = 8 的例子：
| 下标 i | lowbit(i) | c[i] 覆盖的原数组区间 |
|---|---|---|
| 1 | 1 | [1, 1] |
| 2 | 2 | [1, 2] |
| 3 | 1 | [3, 3] |
| 4 | 4 | [1, 4] |
| 5 | 1 | [5, 5] |
| 6 | 2 | [5, 6] |
| 7 | 1 | [7, 7] |
| 8 | 8 | [1, 8] |
从这张表可以看出，树状数组并不是一颗严格意义上的二叉树，而是一棵基于二进制的“索引树”。更新某个位置时，需要向上合并到所有包含该位置的 c[j]；查询前缀和时，则沿着区间边界向左累加。这个过程中下标变化完全由 lowbit 决定。
理解交换律：更新操作i += lowbit(i)是从当前节点跳到它上层的覆盖区间；查询操作i -= lowbit(i)是从当前节点跳到左侧相邻区间。这个方向相反的设计，正是树状数组能在 log n 级别完成操作的原因。
1.3 树状数组、前缀和数组与线段树的对比
在设计方案时，需要知道树状数组的边界。下面表格对比三种常见做法：
| 方案 | 单点更新复杂度 | 前缀查询复杂度 | 区间查询复杂度 | 实现难度 | 适用场景 |
|---|---|---|---|---|---|
| 普通数组 | O(1) | O(n) | O(n) | 极低 | 几乎不更新，只做全量扫描 |
| 前缀和数组 | O(n) | O(1) | O(1) | 极低 | 更新很少，查询非常频繁 |
| 线段树 | O(log n) | O(log n) | O(log n) | 较高 | 复杂区间问题，如区间最值、懒标记 |
| 树状数组 | O(log n) | O(log n) | O(log n) | 低 | 单点更新 + 前缀/区间和场景 |
树状数组最大的特点是用极简代码换来了接近线段树的效率。它不是万能的，例如要求区间最大值、区间最小值时，树状数组处理起来会更麻烦，因为最值不满足加法可逆性。但在“和”这个语义下，树状数组往往是最优先考虑的备选结构。
2. 树状数组的代码骨架：单点更新与前缀查询
2.1 环境与语言选型
下面示例使用 C++ 和 Python 两种语言，核心逻辑完全一致。C++ 版本更适合算法竞赛，Python 版本更适合快速验证思路。无论使用哪种语言，树状数组的下标都必须从 1 开始，否则 lowbit 和更新路径会出错。
如果是学习环境，建议先在一个包含数组长度 n 和若干修改、查询操作的本地文件中调试。如果是生产环境，还需要关注数据范围、整数溢出、并发访问等额外问题。下面先给出最小可运行的模板。
2.2 基础数组结构定义
树状数组只需要一个一维数组tree，长度至少为 n + 1（下标 1 到 n）。初始化时所有元素为 0。原数组可以不保留，直接通过 add 操作把每个元素加入树中。
#include <bits/stdc++.h> using namespace std; const int MAXN = 100005; int tree[MAXN]; int n; inline int lowbit(int x) { return x & -x; } void add(int idx, int delta) { while (idx <= n) { tree[idx] += delta; idx += lowbit(idx); } } int prefixSum(int idx) { int sum = 0; while (idx > 0) { sum += tree[idx]; idx -= lowbit(idx); } return sum; } int rangeSum(int l, int r) { return prefixSum(r) - prefixSum(l - 1); }Python 版本使用列表，数组长度需要 n + 1，实际使用的是下标 1 到 n。
class Fenwick: def __init__(self, n): self.n = n self.tree = [0] * (n + 1) def lowbit(self, x): return x & -x def add(self, idx, delta): while idx <= self.n: self.tree[idx] += delta idx += self.lowbit(idx) def prefix_sum(self, idx): ans = 0 while idx > 0: ans += self.tree[idx] idx -= self.lowbit(idx) return ans def range_sum(self, l, r): return self.prefix_sum(r) - self.prefix_sum(l - 1)2.3 add 操作：自底向上更新
add(idx, delta)的作用是把原数组下标 idx 的位置增加 delta，并同步更新所有覆盖这个位置的树状数组节点。由于 c[i] 覆盖的是[i - lowbit(i) + 1, i]，所以如果一个节点 j 覆盖了 idx，那么必须存在某个路径能从 idx 一步步走到 j。这个路径就是不断执行idx += lowbit(idx)。
以 n = 8、更新 idx = 3 为例：
- 初始 idx = 3，lowbit(3) = 1，更新 tree[3]。
- idx = 4，lowbit(4) = 4，更新 tree[4]。
- idx = 8，lowbit(8) = 8，更新 tree[8]。
- idx = 16，超过 n，结束。
可以看到，更新位置 3 时，覆盖该位置的下标是 3、4、8。这些下标正好对应二进制 0011 -> 0100 -> 1000 的进位方向。这就是为什么树状数组又叫二进制索引树。
2.4 query 操作：自顶向下累加
prefixSum(idx)求的是原数组 [1, idx] 的和。它的拆解过程是：从当前 idx 开始，把 tree[idx] 累加到答案，然后让 idx 跳到下一个未覆盖的左侧区间，直到 idx 变成 0。
以查询前缀和到下标 7 为例：
- idx = 7，lowbit(7) = 1，累加 tree[7]（对应区间 [7, 7]）。
- idx = 6，lowbit(6) = 2，累加 tree[6]（对应区间 [5, 6]）。
- idx = 4，lowbit(4) = 4，累加 tree[4]（对应区间 [1, 4]）。
- idx = 0，结束。累加的结果就是 [1, 4] + [5, 6] + [7, 7] = [1, 7]。
7 的二进制是 0111，查询过程中下标依次变成 0110、0100、0000，每次减去最低位的 1。所以查询的本质是剥离二进制最低位的 1，而更新则是不断向最高位进位。两个操作正好互补。
2.5 区间和查询
因为前缀和可以写成 prefixSum(r) - prefixSum(l - 1)，树状数组可以轻松支持区间查询。这里要注意 l 的下界是 1，不能传 0，否则 prefixSum(0) 会在循环中直接返回 0，但 l - 1 = 0 没有问题。实际区间查询时，如果 l 可能为 1，计算prefixSum(l - 1)时传的就是 0，函数内 while 不执行，直接返回 0，结果是正确的。
写一个简单的验证过程：
int a[] = {0, 1, 2, 3, 4, 5}; // 下标从 1 开始：a[1]=1, a[2]=2, a[3]=3, a[4]=4, a[5]=5 n = 5; memset(tree, 0, sizeof(tree)); for (int i = 1; i <= n; i++) { add(i, a[i]); } printf("%d\n", rangeSum(2, 4)); // 2 + 3 + 4 = 9验证时不仅要看输出结果是否等于 9，还可以手动模拟 add 后的 tree 数组，确认每一步累加区间是否正确。如果结果偏大或偏小，优先检查下标是否从 1 开始、数组是否越界、以及 lowbit 是否写成了x & (x - 1)（这个表达求的是移除最低位 1 之后的值，不是 lowbit）。
3. 树状数组的常见应用：逆序对与计数场景
3.1 用权值树状数组求逆序对
逆序对定义：数组 a 中，如果 i < j 且 a[i] > a[j]，则 (i, j) 是一个逆序对。朴素做法是双重循环，时间复杂度 O(n^2)。使用树状数组时，思路是把“值”当作下标，构建权值树状数组，统计每个值出现的次数。
一种常用遍历方式是从右往左扫描原始数组。对于当前元素 a[i]，需要知道在它右边已经出现过的元素中，有多少个比它小。这正好等于当前权值树状数组中下标 [1, a[i] - 1] 的累计次数。统计完这个数量后，再把 a[i] 的出现次数加 1。
例如数组[3, 1, 2]：
- 从右往左，先处理 2，统计比 2 小的数，当前没有，ans += 0，然后 add(2, 1)。
- 处理 1，统计比 1 小的数，当前没有，ans += 0，然后 add(1, 1)。
- 处理 3，统计比 3 小的数，当前已经出现了 1 和 2，共 2 个，所以 ans += 2。
最后 ans = 2，对应的逆序对是 (3,1) 和 (3,2)，正确。
这里的关键是权值树状数组的下标范围由值域决定。如果 a[i] 的范围很大，比如达到 1e9，就不能直接开这么大的数组，必须先离散化。
3.2 离散化处理大数值
离散化的本质是把原始数值映射到连续的小范围下标。由于我们只关心数值之间的大小关系，所以可以排序后去重，再把每个数映射为它在有序数组中的排名。
vector<int> v(a.begin(), a.end()); sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end()); for (int i = 0; i < n; i++) { int rank = lower_bound(v.begin(), v.end(), a[i]) - v.begin() + 1; // 使用 rank 作为权值树状数组的下标 }如果数组里有重复值，所有相同的值会映射到同一个 rank，因此在统计逆序对时，从右往左遍历需要先查询再更新。如果先更新再查询，会把等于当前值的元素也计入“比当前值小”的数量，导致错误。
离散化后的树状数组大小只需要等于去重后的元素个数 m，不需要关心原始值域。下面给出完整 C++ 逆序对代码：
long long inversionCount(vector<int>& a) { vector<int> v = a; sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end()); int m = v.size(); Fenwick bit(m); // 自行实现，n = m long long ans = 0; for (int i = a.size() - 1; i >= 0; i--) { int rank = lower_bound(v.begin(), v.end(), a[i]) - v.begin() + 1; ans += bit.prefix_sum(rank - 1); bit.add(rank, 1); } return ans; }注意 ans 要用 long long，因为逆序对数量最大可能是 n * (n - 1) / 2，在 n 较大时超出 int 范围。
3.3 逆序对v2：树状数组上的二分统计
在一些题解和算法视频里，逆序对 v2 通常指在树状数组上使用二分查找来优化某些统计过程。例如，给定一个排列，要找到第 k 小的元素所在位置，或者在动态插入元素的过程中维护全局第 k 小。这类问题如果只依赖普通prefix_sum，需要循环查询每个位置，复杂度是 O(n log n) 或更差。
利用树状数组的二进制结构，可以在 O(log n) 时间内完成“找到第一个前缀和大于等于 k 的下标”，也就是动态集合中的第 k 小元素。这个操作并不需要额外写一个二分搜索框架，而是从二进制高位到低位逐位构造答案。下一节详细说明。
逆序对 v2 的一个常见场景是：先通过离散化建立权值树状数组，然后一边插入元素、一边用树状数组上的二分查询某个排名的位置，从而在 O(n log n) 内完成逆序对统计和排名维护。这里要特别注意的是，prefix_sum(i)返回的是小于等于 i 的元素个数，因此第 k 小对应的位置是findKth(k)，而逆序对统计需要的是当前值左侧有多少个更大的元素，需要结合扫描方向灵活转换。
4. 树状数组上的二分：第 K 小与排名查询
4.1 问题定义：在动态集合中找第 K 小
假设一个初始为空的可重集合，支持两种操作：插入一个值，查询当前集合中第 k 小的元素。朴素做法是维护一个有序数组，插入时找到位置并移动元素，最坏 O(n)。使用优先队列只能快速得到最值，无法直接回答第 k 小。使用平衡树可以实现，但实现复杂。
如果值域已知且不大，可以用权值树状数组。第 k 小的问题可以转化为：在权值树状数组上，找到一个最小的下标 idx，使得prefix_sum(idx) >= k。换句话说，从左到右累加每个值出现的次数，当累计次数第一次达到 k 时，当前值就是第 k 小元素。
4.2 二分的两种实现方式
第一种方式最直观：在 [1, m] 上做普通的整数二分，每次用prefix_sum(mid)判断是否大于等于 k。这样单次查询复杂度是 O(log m * log m)，即 O(log^2 n)。这种方式容易理解，适合确认思路，但在 n 很大且查询次数很多时不够高效。
第二种方式利用树状数组每个节点覆盖区间的特点，从最高位开始向下枚举二进制位。设pos当前构造出的答案，初始为 0，cnt为已累计的个数，初始为 0。倒序枚举最大的二进制位2^p，判断pos + 2^p是否越界，以及cnt + tree[pos + 2^p]是否小于 k。如果仍小于 k，说明目标位置在右侧，可以累加这一段，然后让 pos 加上2^p。枚举结束后，pos + 1 就是第 k 小元素的下标。这个方法的本质是把普通二分替换成基于二进制位的倍增查找，复杂度为 O(log n)。
4.3 模板代码实现
// 查找第一个前缀和 >= k 的下标，k 至少为 1 // tree 是权值树状数组，n 是值域大小 int findKth(int k) { int pos = 0; // 最大的不超过 n 的 2 的幂，也可以使用 log2(n) 或预处理 int maxPow = 1; while (maxPow <= n) maxPow <<= 1; maxPow >>= 1; for (int step = maxPow; step; step >>= 1) { int next = pos + step; if (next <= n && tree[next] < k) { k -= tree[next]; pos = next; } } return pos + 1; }这里使用的是递归式二进制拆分：tree[next]保存的是区间(pos, pos + step]的累计次数。如果这段区间里的总数仍然小于 k，说明第 k 小在更右边的区间，于是从 k 中减掉这段数量，并移动 pos。
对照一下，维护一个支持插入和查询第 k 小的完整类可以写成：
struct DynamicKth { int n; vector<int> tree; DynamicKth(int n) : n(n), tree(n + 1, 0) {} void add(int idx, int delta) { while (idx <= n) { tree[idx] += delta; idx += idx & -idx; } } int findKth(int k) { int pos = 0; int maxPow = 1; while (maxPow <= n) maxPow <<= 1; maxPow >>= 1; for (int step = maxPow; step; step >>= 1) { int next = pos + step; if (next <= n && tree[next] < k) { k -= tree[next]; pos = next; } } return pos + 1; } };使用示例：假设值域范围是 [1, 5]，依次插入 3、1、3、2，再查询第 3 小。树状数组中每个位置的次数分别为 [1, 1, 2, 0, 0]，前缀和依次为 [1, 2, 4, 4, 4]，所以第 3 小是值 3。运行findKth(3)应该返回 3。
4.4 与平衡树 / 线段树上二分的对比
树状数组上的二分只能处理可加且可逆的统计信息，比如元素个数、和。平衡树可以同时维护排名、前驱、后继、区间翻转等更复杂信息，但实现复杂度高。线段树上二分也能实现类似功能，但需要存储左右子树，代码更重。
| 方案 | 插入/删除复杂度 | 查第K小复杂度 | 实现工作量 | 适用值域 |
|---|---|---|---|---|
| 平衡树 | O(log n) | O(log n) | 高 | 任意 |
| 线段树 + 二分 | O(log n) | O(log n) | 中 | 离散化后的值域 |
| 树状数组 + 二进制倍增 | O(log n) | O(log n) | 低 | 离散化后的值域 |
如果只做“动态集合插入 + 查询第 k 小”，树状数组方案足够好用。如果需要删除、查找前驱后继，那么树状数组也能通过计数数组配合 prefix_sum 二分完成一部分，但代码会复杂一些。
5. 常见问题与排查路径
5.1 下标从 0 开始导致的死循环或错误
树状数组的所有操作都要求下标从 1 开始。如果原数组下标从 0 开始，直接使用会出错。例如add(0, delta)时，因为0 & -0等于 0，idx += 0，循环永不结束，程序卡死。
解决方案：在所有原始下标上统一加 1。如果题目给定的是下标从 1 开始，就不需要改。如果是从 0 开始的数组，那么在调用 add、query 时记得把传入下标转换为 1-based。
5.2 lowbit 计算错误
lowbit(x) = x & -x。有人会写成x & (x - 1)，这两个结果完全不同。x & (x - 1)会把最低位的 1 清零，得到的是移除了最低位 1 之后的值。例如 x = 6，x & -x是 2，而x & (x - 1)是 4。后者会导致更新和查询路径错乱。
排查方式：输出几个典型值的 lowbit，与预期对比。可以用这段代码检查：
for (int i = 1; i <= 16; i++) { cout << i << " " << (i & -i) << endl; }期望结果是 1、2、1、4、1、2、1、8、1、2、1、4、1、2、1、16。
5.3 离散化时排序去重错误
离散化前必须排序并去重。如果去重后仍用原始值作为下标，可能导致数组越界。另外，lower_bound返回的迭代器减v.begin()得到的是从 0 开始的排名，因此要加 1 才能作为树状数组下标。
常见错误：
int rank = lower_bound(v.begin(), v.end(), a[i]) - v.begin(); // 错误，应为 +1 bit.add(rank, 1);如果 rank 为 0，add 会陷入死循环。这也解释了为什么凡是使用lower_bound求排名时，都必须加 1。
5.4 更新后查询结果不对
先确认更新是否正确。树状数组的 add 只修改了受影响节点，不修改原数组。如果你一边用a[i]直接取值，一边又用 tree 查询，就可能出现不一致。推荐做法是：原数组只保存真实数据，树状数组只负责前缀和信息。如果原始数据变化，必须同步调用 add。
另外，如果树状数组的 add 和 query 使用了不同的 n 作为边界，会导致某些操作没有覆盖到正确区间。比如 add 用 n = 10，query 用 n = 100，虽然语法不报错，但语义已经不对了。
5.5 整数溢出
逆序对数量最大是 n*(n-1)/2，n 稍大就可能超过 2^31-1。树状数组内部假设存储次数，也应使用 64 位整数。C++ 中建议使用long long或int64_t，Python 中整数没有溢出问题，但要注意性能。
5.6 树状数组上二分时的边界
findKth函数要求 k 在 1 到当前总数之间。如果传入了大于总数的 k，算法会返回 n+1，导致访问越界或错误结果。必须在使用前维护一个total变量记录当前元素个数，并在查询前判断。
下面用表格汇总排查顺序：
| 问题现象 | 常见原因 | 检查方式 | 处理建议 |
|---|---|---|---|
| 更新时程序卡死 | 传入下标为 0 | 检查 add 的参数是否可能为 0 | 下标统一加 1 |
| 查询前缀和结果偏小或偏大 | lowbit 写错 | 输出 lowbit 序列对比 | 使用x & -x |
| 离散化后越界 | 排名未加 1 | 检查 rank 值 | 在 lower_bound 结果上加 1 |
| 更新后数据不一致 | 原数组和树状数组不同步 | 打印 tree 数组 | 保证所有修改都走 add |
| 逆序对 ans 溢出 | 使用 int 存储结果 | 查看数据范围 | 改用 long long |
| 二分返回错误位置 | 查询前未判断 k 范围 | 打印 total 和 k | 增加 total 维护和边界判断 |
6. 树状数组的最佳实践与扩展方向
6.1 使用树状数组的最佳实践清单
当你决定使用树状数组时，可以按下面清单检查：
- 确认操作是“单点更新 + 前缀查询”或可以转化为这个模型。
- 确认下标从 1 开始；如果输入从 0 开始，先加 1。
- 所有更新操作统一使用 add，不要直接修改 tree。
- 如果值域大，先排序去重离散化，注意排名加 1。
- 统计类题目用 long long，避免逆序对等数量溢出。
- 树状数组大小设置为 n + 1，并确认 add 的边界是 <= n。
- 使用二分时，先确认 k 在总数范围内。
- 测试时不仅测试查询，还要测试两次更新后的结果，验证动态性。
- 生产环境若有并发写，需要加锁或使用线程安全的更新方式。
- 频繁构造大数组时避免反复初始化，可以只初始化使用过的节点。
6.2 典型变体：区间修改与区间查询
树状数组不仅能做单点更新和区间查询，还能通过差分数组实现区间修改和单点查询。具体做法是：维护原数组 a 的差分数组 d，其中 d[i] = a[i] - a[i-1]。对原数组区间 [l, r] 增加 x 等价于对 d[l] 加 x、d[r+1] 减 x。此时单点查询 a[i] 等价于求 d 的前缀和。
如果同时要求区间修改和区间查询，需要维护两个树状数组。设差分数组 d，则原数组 a 的前缀和满足：
sum_{i=1}^n a[i] = sum_{i=1}^n (n - i + 1) * d[i]
通过维护 d[i] 和 i * d[i] 两个树状数组，可以实现在 O(log n) 内完成区间修改、区间查询。这是树状数组最重要的扩展之一。
6.3 二维树状数组
当数据从一维扩展到二维，树状数组也可以变成二维形式。二维树状数组使用tree[x][y]保存一个二维区间和，更新和查询都在 x 和 y 两个维度上分别做 lowbit 跳跃，复杂度为 O(log^2 n)。它适合处理子矩阵和、单点修改、区域查询等问题。
如果题目数据范围很大，二维数组无法直接开，可以使用离散化、映射、离线处理或稀疏存储。实际工程中，二维树状数组更常出现在图像处理、地理信息统计等需要按区域聚合的场景。
6.4 与排序、哈希、离散化组合
树状数组最强大的地方在于和排序、哈希、离散化组合。当值域无法确定时，先做离散化；当需要按出现次数排名时，使用权值树状数组；当需要统计区间内不同元素个数时，可以离线按右端点排序，结合树状数组维护最近出现位置。这些组合让树状数组远远不止“求前缀和”这么简单。
例如求静态数组每个区间内不同数字的个数，可以把查询按右端点排序，从左往右扫描，每个数字只在其最后一次出现的位置贡献 1，其余出现位置先减再加。这样的离线处理配合树状数组，可以高效回答大量区间查询。
6.5 学习路径与练习建议
树状数组的学习路径建议如下：
- 先手工模拟一个长度为 8 的数组，手动执行 add 和 query，画出每次下标移动。
- 用模板解决纯前缀和与单点更新问题，比如洛谷 P3374。
- 用权值树状数组解决逆序对问题，注意离散化。
- 实现树状数组上的 findKth，用它做动态第 k 小。
- 学习差分数组，实现区间修改 + 单点查询。
- 再挑战区间修改 + 区间查询，理解两个树状数组的维护方式。
- 最后接触二维树状数组和离线查询问题。
从练习角度看，树状数组比线段树更容易掌握，而且代码稳定。推荐先大量手写模板，直到能在一分钟内无错误写出 add、query、findKth 三个函数。之后再学线段树，你会发现线段树的很多区间合并思想与树状数组有相通之处，但树状数组的简洁性依旧不可替代。实际项目中遇到单点更新加前缀统计的场景，优先考虑树状数组，而不是一上来就堆线段树。这样写出来的代码更短、更容易维护，也更容易被同事读懂。
