企业官网建设流程全解析

树状数组（Binary Indexed Tree，简称 BIT）在算法竞赛里的地位很特别：代码短、常数小、思路直观，但真正上手做题的时候，很多人会在差分、离散化、边界更新这些细节上反复翻车。这篇文章想解决的问题很直接：从基础到进阶，用 6 道模板题把 BIT 的核心玩法完整过一遍。如果你正准备系统刷数据结构，或者感觉自己树状数组只会背板子，建议把这 6 道题亲手做一遍，做完之后再去看各种变形题，会有完全不同的感觉。

这 6 道题覆盖了 BIT 最典型的几类场景：单点修改加区间查询、差分配合区间修改、双 BIT 实现区间修改加区间查询、逆序对与离散化、二维 BIT、值域 BIT 上的二分找第 K 小。每一步我都会讲清楚背后的推导逻辑、完整代码和踩坑点。我尽量不堆术语，用“为什么这样写”和“哪里容易出错”的方式来讲，代码以 C++ 为主，但思路对所有语言通用。

1. 先把 BIT 的底层逻辑讲明白：lowbit 与管辖区间

很多人学树状数组，上来就抄两个循环：一个向上更新、一个向下求和。抄几遍确实能记住，但一旦题目稍微变形，比如从单点修改变成区间修改，从一维变成二维，从求和变成计数，就不知道该怎么改。所以第一步，花点时间把 BIT 的“管辖区间”彻底搞清楚。

1.1 lowbit 到底在干什么

树状数组本质上是一个普通数组 c[1..n]，其中 c[i] 保存的是原数组 a 中某一段连续区间的和，而这一段区间的长度恰好是 lowbit(i) = i & (-i)。

举例说明：

可以发现一个规律：c[i] 管的是从i - lowbit(i) + 1到i这段区间。也就是说，i 的二进制里最低位的那个 1，决定了它管多长一段。8 的二进制是 1000，最低位的 1 在最高位，所以它管前面 8 个；6 的二进制是 0110，最低位的 1 在第二位，代表长度 2，所以它只管 a[5..6]。

为什么这个结构好用？因为任意一个前缀 [1..x] 都能被拆成 O(log n) 个互不重叠的管辖区间，且这个拆分和 x 的二进制中 1 的个数完全对应。举个例子，查询 sum(13)，13 的二进制是 1101，拆成：

• c[13]，对应二进制最低位的 1，管 [13..13]
• c[12]，对应第二位的 1，管 [9..12]
• c[8]，对应最高位的 1，管 [1..8]

三个区间恰好覆盖 [1..13]，而且没有重叠。这就是 BIT 查询只需要 O(log n) 的原因——二进制里有几个 1，就合并几个区间。

1.2 前缀和查询和单点更新的循环规律

理解了管辖区间，两个核心函数就能自己写出来了。

查询前缀和 sum(x)：不断把 x 的最低位 1 去掉，累加对应区间的值。去掉最低位 1 的写法是x -= x & (-x)。

更新单点 add(x, v)：修改 a[x] 会影响哪些 c 节点？所有管辖区间包含 x 的节点都要改。观察表格，a[5] 属于 c[5]、c[6]、c[8]、c[16]……规律是x += x & (-x)。为什么是向上加 lowbit？因为 c[x] 管到区间 [x - lowbit(x) + 1, x]，而它的父节点，也就是能够覆盖这个区间的最小节点，下标正好是 x + lowbit(x)。

int bit[N]; void add(int x, int v) { for (int i = x; i <= n; i += i & (-i)) bit[i] += v; } long long sum(int x) { long long res = 0; for (int i = x; i > 0; i -= i & (-i)) res += bit[i]; return res; }

注意两个循环的边界：add 里是i <= n，sum 里是i > 0。这里的 n 是 BIT 的总大小，不是查询的 x。很多人第一次写容易把 add 也写成i <= x，这样更新就只在一小段里打转，查询结果自然不对。

1.3 O(n) 建树和初始化

单点更新 n 次建树，复杂度是 O(n log n)，n 到 1e5 或 1e6 时能接受。但存在一种 O(n) 的建法，重要的是理解它的原理，而不是死记代码。

先把 c[i] 初始化为 a[i]，然后自底向上累加：对每个 i，它的父节点是 j = i + lowbit(i)，把 c[i] 累加到 c[j] 上。因为每个 c[i] 本来就是一段原始区间的和，向上累加一次，就把所有子区间的贡献合并到了父节点。

for (int i = 1; i <= n; ++i) { bit[i] += a[i]; // bit 初始为 0，直接累加原值 int j = i + (i & (-i)); if (j <= n) bit[j] += bit[i]; }

其实还有一种实现更容易理解：先算原数组前缀和 pre，然后bit[i] = pre[i] - pre[i - lowbit(i)]。这个写法也能 O(n) 建树，而且公式直接对应“管辖区间和”的定义。两种方法写哪种都行，但建议至少把第一种背熟，因为它在很多题目里能直接用来初始化维护差分数组的 BIT。

到这里，BIT 最基础的两个函数已经齐了。接下来用模板题来验证理解。

2. 前两道基础模板题：单点修改区间查询与差分版区间修改

这一章的题目，我习惯叫它“BIT 入门必写的两道题”，一道是单点修改加区间查询，另一道是区间修改加单点查询。这两道题本身没有难度，但它们背后藏着 BIT 最重要的两种使用形态：直接维护原数组，或者维护差分数组。

2.1 T1 单点修改 + 区间查询

题目描述很经典：给定一个长度为 n 的数组，初始值已知。接下来有 q 次操作，操作有两种：

• 1 x v：把 a[x] 加上 v
• 2 l r：查询 a[l] 到 a[r] 的和

如果只会暴力，单次操作是 O(n)，q 次就是 O(nq)。用 BIT 的话，单点修改和前缀查询都是 O(log n)。

这应该是所有 BIT 模板题里最基础的一道。代码直接用上一节的 add 和 sum 就行，唯一要注意的是区间查询的转换：query(l, r) = sum(r) - sum(l - 1)。记住前缀和是包含 x 的，所以左边界要减一。

#include <bits/stdc++.h> using namespace std; const int N = 1000005; int n, q; long long bit[N]; void add(int x, long long v) { for (int i = x; i <= n; i += i & (-i)) bit[i] += v; } long long sum(int x) { long long res = 0; for (int i = x; i > 0; i -= i & (-i)) res += bit[i]; return res; } int main() { scanf("%d%d", &n, &q); for (int i = 1; i <= n; ++i) { int x; scanf("%d", &x); add(i, x); } while (q--) { int op; scanf("%d", &op); if (op == 1) { int x; long long v; scanf("%d%lld", &x, &v); add(x, v); } else { int l, r; scanf("%d%d", &l, &r); printf("%lld\n", sum(r) - sum(l - 1)); } } return 0; }

数据规模再大一点，比如 n、q 到 1e6，scanf/printf 也够用。我见过用 cin/cout 然后没关同步直接超时的，这类比赛题还是老老实实 scanf 或自定义快读比较稳。

2.2 T2 区间修改 + 单点查询：差分数组接入 BIT

第二道题看起来更难一点：区间修改，单点查询。也就是说：

• 1 l r v：a[l] 到 a[r] 每个数都加上 v
• 2 x：查询 a[x] 当前的值

如果不做任何转化，BIT 单点更新很快，区间更新就很尴尬。解决办法是用差分数组 d，其中d[i] = a[i] - a[i-1]。

区间 [l, r] 同时加 v，在差分数组里只会影响两个位置：d[l] += v，d[r+1] -= v。查询 a[x] 的时候，只需要求差分数组 [1..x] 的前缀和，因为a[x] = d[1] + d[2] + ... + d[x]。

这相当于把一个“区间操作”转换成两个“单点操作”，把“单点查询”转换成一个“前缀查询”。BIT 擅长什么？单点修改和前缀查询。所以差分正好把题目变成 BIT 的主场。

#include <bits/stdc++.h> using namespace std; const int N = 500005; int n, q; long long bit[N]; void add(int x, long long v) { for (int i = x; i <= n; i += i & (-i)) bit[i] += v; } long long sum(int x) { long long res = 0; for (int i = x; i > 0; i -= i & (-i)) res += bit[i]; return res; } int main() { scanf("%d%d", &n, &q); long long pre = 0; for (int i = 1; i <= n; ++i) { long long x; scanf("%lld", &x); add(i, x - pre); // 读入的是原数组，插入的是差分值 pre = x; } while (q--) { int op; scanf("%d", &op); if (op == 1) { int l, r; long long v; scanf("%d%d%lld", &l, &r, &v); add(l, v); add(r + 1, -v); } else { int x; scanf("%d", &x); printf("%lld\n", sum(x)); } } return 0; }

注意初始化方式：读第 i 个数时，往 BIT 里插入的是a[i] - a[i-1]，我上面用变量 pre 记录前一个值。这样做的好处是，后面所有区间修改操作都建立在同样的差分逻辑上，不会出现“原数组和差分数组混用”的混乱。

2.3 两道基础题最容易丢分的三个小坑

第一，数组下标从 1 开始。BIT 的标准写法默认下标从 1 开始，0 号位置是虚拟根。如果你从 0 开始读入数据，add(0, v) 会进入死循环，因为0 + (0 & -0)恒等于 0。所以这类模板题，读入和操作统一从 1 开始，宁可在前面留一个空位。

第二，差分更新边界。区间 [l, r] 加 v，一定要记得在 r+1 的位置减 v。这里的 r+1 如果正好等于 n+1，循环条件i <= n不会进入，所以代码上不用特判。但我见过有人画蛇添足写if (r + 1 <= n) add(r + 1, -v)，这没问题，只是没必要；真正危险的是漏掉这个更新，导致从 l 之后所有位置都加上 v。

第三，数据类型。T1 的区间和、T2 的差分累加都可能超出 int 范围。n 到 1e5，a 到 1e9，区间和轻松超过 2^31。从模板阶段就把 BIT 数组开成 long long，后面能少踩很多坑。

顺带提一句：这两道题也是很多同学第一次接触到“ODT 思想”和“差分思想”的入口。差分这个技巧本身非常通用，后面区间修改区间查询、扫描线、莫队里都会反复用到。

3. 区间修改 + 区间查询：一个 BIT 不够，那就上两个

前两道题合起来，很容易产生一个想法：能不能用 BIT 同时做到区间修改和区间查询？既然单点修改区间查询用一个 BIT，区间修改单点查询用差分 BIT，那区间修改区间查询是不是可以用两个 BIT？

答案是肯定的。这是 BIT 进阶的第一道坎，也是理解“BIT 不止能维护原数组，还能维护加权信息”的关键。

3.1 从差分推导到双 BIT 维护

沿用 T2 的差分数组 d，d[i] = a[i] - a[i-1]，那么：

• 区间 [l, r] 加 v：d[l] += v，d[r+1] -= v
• a[x] 的值：d[1] + d[2] + ... + d[x]

现在要算的不是 a[x]，而是 a[1] + a[2] + ... + a[x]，也就是前缀和。用求和符号写一遍：

sum_{i=1}^{x} a[i] = sum_{i=1}^{x} sum_{j=1}^{i} d[j]

交换求和顺序，d[j] 在 [j, x] 范围内被累加了 (x - j + 1) 次：

= sum_{j=1}^{x} d[j] * (x - j + 1)

= (x + 1) * sum_{j=1}^{x} d[j] - sum_{j=1}^{x} j * d[j]

这个式子说明，只要同时维护两个前缀和：sum(d[j])和sum(j * d[j])，就能 O(1) 算出 a 数组的前缀和。于是区间查询 [l, r] 就是前缀和 [1..r] 减去 [1..l-1]。

所以开两个 BIT：bit1 存 d[j]，bit2 存 j * d[j]。区间修改时，对 bit1 做两次单点更新，对 bit2 也做两次单点更新，但第二个值的系数要对应好：

• 位置 l 加 v：bit1.add(l, v)，bit2.add(l, l * v)
• 位置 r+1 减 v：bit1.add(r+1, -v)，bit2.add(r+1, -(r+1) * v)

查询前缀和 sum(x) 时：

long long query_prefix(int x) { return (x + 1) * sum(bit1, x) - sum(bit2, x); }

这里 sum 是单 BIT 的前缀和函数，但两个 BIT 不同名，需要把数组指针传进去。

3.2 T3 完整实现与复杂度分析

题目描述：给定 n 个数的数组，q 次操作：

• 1 l r v：区间 [l, r] 每个数加 v
• 2 l r：查询 [l, r] 的区间和

#include <bits/stdc++.h> using namespace std; const int N = 200005; int n, q; long long bit1[N], bit2[N]; void add(long long bit[], int x, long long v) { for (int i = x; i <= n; i += i & (-i)) bit[i] += v; } long long sum(long long bit[], int x) { long long res = 0; for (int i = x; i > 0; i -= i & (-i)) res += bit[i]; return res; } long long get_prefix(int x) { return (x + 1) * sum(bit1, x) - sum(bit2, x); } int main() { scanf("%d%d", &n, &q); long long pre = 0; for (int i = 1; i <= n; ++i) { long long x; scanf("%lld", &x); add(bit1, i, x - pre); add(bit2, i, i * (x - pre)); pre = x; } while (q--) { int op; scanf("%d", &op); if (op == 1) { int l, r; long long v; scanf("%d%d%lld", &l, &r, &v); add(bit1, l, v); add(bit2, l, l * v); add(bit1, r + 1, -v); add(bit2, r + 1, -(r + 1) * v); } else { int l, r; scanf("%d%d", &l, &r); printf("%lld\n", get_prefix(r) - get_prefix(l - 1)); } } return 0; }

时间复杂度：每次操作都是常数额外开销的 4 次 BIT 更新或 2 次 BIT 查询，单次 O(log n)。空间复杂度 O(n)。两个 BIT 各占一个 long long 数组，和线段树的 4 倍空间相比优势明显。

有一个容易写错的地方：bit2 插入差分初始值时，乘的是 i，不是 x。比如第 4 个位置差分值是 d，那 bit2 要加的是4 * d，不是get_prefix(4)里那个 4。我在给 A 同学讲这题时，发现他 debug 了很久，就是因为初始化时忘乘 i。

3.3 为什么不直接用线段树

很多人看到区间修改加区间查询，第一反应是线段树。确实线段树能解决这个问题，而且还能处理区间最值、区间赋值等更复杂的操作。

但 BIT 在这个场景有两个不可忽视的优势：第一，代码量只有线段树的一半左右，比赛里手写出错概率更低；第二，常数更小，同样的 O(log n)，BIT 的更新是循环里加个 lowbit，线段树是递归加回溯，在 q 到 1e6 的时候差距很明显。

不过要清醒：BIT 这套双数组做法依赖的是“求和操作可减”。如果题目要求区间修改加区间最大值查询，双 BIT 就做不到，因为最大值没有相反数，不能靠差分抵消。这时候还是得乖乖写线段树。

很多变形题其实是在试探你“能不能把问题化归到可减运算”。比如维护区间平方和，如果能维护区间和和区间平方和，区间加 v 之后平方和的变化量是 2v*和 + 区间长度*v^2，这就能用 BIT 做。这类题看到的第一反应应该是拆公式，而不是直接套线段树。

4. 逆序对：BIT 与离散化第一次真正配合

树状数组除了维护区间和，还有一个应用频率极高的场景：值域统计。逆序对是最典型的代表题，也是 BIT 从“模板”走向“活用”的一道分水岭。

4.1 暴力和 BIT 的差距

题目很简单：给定长度为 n 的数组 a，求有多少对 (i, j) 满足 i < j 且 a[i] > a[j]。n 到 1e5，a[i] 可以到 1e9。

暴力两重循环是 O(n^2)，n 到 1e5 直接爆掉。经典分治解法是归并排序，同样 O(n log n)。树状数组做法的核心思想是：把数组 a 的每个值看成一个“桶”，从左到右扫描，一边统计“我已经见过的数里，有几个比当前值大”，一边把自己塞进桶里。

如果从右往左扫描，统计的是“右边已经出现过的数里，有几个比当前值小”。两种方向等价，代码写法和边界细节略有差别，下面统一用从右往左的版本。

4.2 离散化的具体流程与等值处理

a[i] 最大到 1e9，不可能直接开一个 1e9+5 的 BIT。解决方案是离散化：把所有出现过的数排序去重，得到数组 b，每个原数值映射到它排序后的排名 rank，范围压缩到 1 到 m，m 是去重后数值个数。之后 BIT 的下标就是 rank。

离散化的三个步骤：

1. 复制原数组到 b，排序。
2. 用 unique 去重，m 就是去重后的长度。
3. 每个原值通过 lower_bound 在 b 里找位置，得到 1 到 m 的排名。

有一个细节非常关键：相同数值的逆序对不算。比如数组 [2, 2]，应该输出 0，不是 1。如果两个相等的数离散化成不同排名，就会错误地算成一组逆序对。解决办法是把相同数值映射到同一个排名。用 lower_bound 天然满足这一点，因为同一个值查出来的迭代器下标一样。

那么统计时，如果从右往左扫描，查“严格比当前值小的数有几个”，应该用 sum(rank - 1)，而不是 sum(rank)。sum(rank) 会把已经插入的相等值也算进来，答案就偏大。

4.3 T4 完整代码与两种遍历方向的选择

#include <bits/stdc++.h> using namespace std; const int N = 100005; int n; long long ans; long long bit[N]; vector<long long> all; long long a[N]; void add(int x, int v) { for (int i = x; i <= n; i += i & (-i)) bit[i] += v; } long long sum(int x) { long long res = 0; for (int i = x; i > 0; i -= i & (-i)) res += bit[i]; return res; } int get_rank(long long x) { return lower_bound(all.begin(), all.end(), x) - all.begin() + 1; } int main() { scanf("%d", &n); for (int i = 1; i <= n; ++i) { scanf("%lld", &a[i]); all.push_back(a[i]); } sort(all.begin(), all.end()); all.erase(unique(all.begin(), all.end()), all.end()); // 从右往左扫描：统计右边已出现且严格小于当前值的元素个数 for (int i = n; i >= 1; --i) { int pos = get_rank(a[i]); ans += sum(pos - 1); add(pos, 1); } printf("%lld\n", ans); return 0; }

注意答案最大是 n*(n-1)/2，n = 1e5 时大约是 5e9，超过 int。我见过有人 ans 用 int，最后输出负数，排查半天发现是类型问题。

向左扫描版本也提一下：从左往右，已插入的数是“左边”的数，对当前位置，比它大的个数等于已插入总数减去小于等于它的个数，即i - 1 - sum(pos)。这个写法里 sum(pos) 包含了相等的值，所以也没问题，因为相等的数在左边，本来就该算作不大于它。如果想用 sum(pos - 1) 来统计，那统计的是左边严格小于它的个数，两者均可，只是含义不同。

最后补充一句：逆序对模板的价值远远不止这一道题。它是“用 BIT 做离线统计”的原型。后面很多题，包括求每个数前面有多少个比它大的数，统计区间内不同元素个数，都可以从这道题的思路延伸出去。

5. 二维 BIT 与值域树状数组：从模板题走向变形题

如果说前四道题还都在“数组上跑”，那第五题和第六题开始，就是 BIT 的两种进阶形态：二维化和在值域上二分。这两类问题在竞赛里出现频率很高，值得单独拉出来讲。

5.1 T5 二维 BIT 的单点更新与子矩阵查询

二维 BIT 的引入很自然：一维 BIT 是每层一维数组，二维 BIT 就是每层再套一个 BIT，也就是二维数组 tree[n+1][m+1]。

• 单点更新 (x, y) 加 v：两层循环，外层 i 从 x 开始向上 lowbit，内层 j 从 y 开始向上 lowbit，每层都执行 tree[i][j] += v。
• 前缀查询 sum(x, y)：同样两层循环，累加所有 tree[i][j]。
• 子矩阵 [x1..x2] x [y1..y2] 的和：用二维容斥，query(x2, y2) - query(x1-1, y2) - query(x2, y1-1) + query(x1-1, y1-1)。

二维容斥和二维前缀和一模一样，不多解释。关键点是坐标从 1 开始。如果题目给的坐标可能是 0，比如 0 到 n-1，要整体平移加 1，否则 x=0 时内层循环会死循环。

#include <bits/stdc++.h> using namespace std; const int N = 1005; long long tree[N][N]; int n, m, q; void add(int x, int y, long long v) { for (int i = x; i <= n; i += i & (-i)) for (int j = y; j <= m; j += j & (-j)) tree[i][j] += v; } long long sum(int x, int y) { long long res = 0; for (int i = x; i > 0; i -= i & (-i)) for (int j = y; j > 0; j -= j & (-j)) res += tree[i][j]; return res; } long long query(int x1, int y1, int x2, int y2) { return sum(x2, y2) - sum(x1 - 1, y2) - sum(x2, y1 - 1) + sum(x1 - 1, y1 - 1); } int main() { scanf("%d%d%d", &n, &m, &q); for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { int x; scanf("%d", &x); add(i, j, x); } } while (q--) { int op; scanf("%d", &op); if (op == 1) { int x, y; long long v; scanf("%d%d%lld", &x, &y, &v); add(x, y, v); } else { int x1, y1, x2, y2; scanf("%d%d%d%d", &x1, &y1, &x2, &y2); printf("%lld\n", query(x1, y1, x2, y2)); } } return 0; }

二维 BIT 的复杂度是 O(log n * log m)。当 n 和 m 都到 1e3，甚至 1e5，二维数组就完全开不下了。这时候有几种应对方案：如果操作很少，可以用离线做法配合一维 BIT 排序扫描；如果矩阵本身很稀疏，可以给每个更新点用哈希表按需开节点，但常数很大。竞赛里遇到二维 BIT，数据范围一般会控制在 n、m 在 1000 级别，超过这个级别就要换思路。

5.2 T6 值域 BIT 上二分：动态第 K 小

第六道题是 BIT 的另一个高光时刻：维护一个可重集合，支持插入、删除、查询第 K 小。这类题目在“动态中位数”“成绩排名动态查询”等场景里非常常见。

思路：把所有可能插入的值离散化到 1..m，然后 BIT 维护的是每个离散化值“出现了多少次”。插入就是 add(pos, 1)，删除就是 add(pos, -1)。查询第 K 小的时候，要在 BIT 上找一个最小的 pos，使得前缀和 >= K。

最快的做法不是二分套 BIT 的 O(log^2 n)，而是直接在 BIT 上做倍增二分，复杂度 O(log n)。

原理：BIT 节点 c[i] 本来就保存了一段区间次数和，我们可以从高到低枚举 2^j，判断“当前位置 pos 加上 2^j 之后的前缀和是否还小于 K”。整个过程类似在 BIT 上走一条从根到叶子的路径。

const int N = 100005; const int LOG = 20; // 根据 m 的范围取，一般取 20 够用 long long bit[N]; int m; // 离散化后的最大值 int find_kth(int k) { int pos = 0; for (int j = LOG; j >= 0; --j) { int nxt = pos + (1 << j); if (nxt <= m && bit[nxt] < k) { pos = nxt; k -= bit[nxt]; } } return pos + 1; // 返回离散化排名 }

这段代码每次循环保持一个不变量：当前目标排在区间 [pos + 1, m] 内，且 pos 之前的前缀和已经小于 K。当所有二进制位试完，pos 就是“最后一个前缀和小于 K 的位置”，所以答案是 pos + 1。如果集合里元素不足 K 个会越界，调用前要记得判断总个数。

为什么bit[nxt] < k这个判断是对的？nxt = pos + 2^j，而 BIT 中节点 nxt 管的是[nxt - lowbit(nxt) + 1, nxt]，也就是上一轮 pos 到 nxt 之间新增的那些区间。由于倍增步长是从大到小，这些区间互不重叠，所以bit[nxt]恰好是这一段区间新增的次数和。

完整例题描述：初始有 n 个数，q 次操作，1 x表示插入 x，2 x表示删除一个 x，3 k表示查询当前集合中第 k 小的数。把所有操作里出现过的 x 都先收集起来离散化，然后按上面的思路在线处理。

这道题看起来简单，实际是面试和比赛里很喜欢考的“在线查询第 K 小”的原型。把它做熟之后，动态中位数、滑动窗口第 K 大、订单系统里实时排名查询的思路都能迁移过去。

5.3 二维 BIT 的空间边界与稀疏写法

二维 BIT 最让人头疼的是空间。普通数组开tree[N][N]，N 到 1e4 就是 1e8 个数，long long 承载不了。如果数据范围偏偏很大，但更新点不多，可以尝试“稀疏 BIT”：不需要 log n * log m 个节点全开，而是给每个需要的坐标动态开辟，通常用 map<pair<int,int>, long long> 或哈希表实现。

不过稀疏 BIT 的常数比较大，而且更新时嵌套 map 很容易写慢。我的经验是：长度 1000 乘以 1000 是极限，能用的场景有限。更实用的是把二维问题离线化，通过排序把一维降掉，再用一维 BIT 扫描。很多“矩阵内有几个点坐标满足 x1<x<x2 且 y1<y<y2”类的问题，都可以用一维 BIT 配合排序和差分离线解决。遇到二维 BIT 开不下时，优先考虑这个方向。

6. BIT 高频翻车现场和我的调试习惯

最后这部分，我把自己和周围人做 BIT 时见过的高频问题集中整理一下。这些问题大多不是“不会思路”，而是“细节爆炸”，而且爆炸原因往往非常统一。

6.1 三种最常见的越界和漏更新

第一种是下标从 0 开始的连环爆炸。BIT 所有下标操作都基于 lowbit，0 的 lowbit 是 0，于是循环永远跳不出去。如果输入数据范围是 0 到 n-1，请记得在读入和查询时对下标加 1。很多模板题的隐藏陷阱就在这里。

第二种是 add 和 sum 的循环边界写反。add 的退出条件是i <= n，sum 的退出条件是i > 0。我见过把 sum 写成i <= x的，也见过 add 写成i <= x的，都会导致统计区间不完整。遇到答案偏小的 bug，先检查这两个边界。

第三种是区间修改忘更新 r+1 边界。T2 里add(r+1, -v)是最容易漏的一行，因为它只在“区间终点”触发，如果测试数据只覆盖部分区间，可能很长一段时间看不出问题。输出偏大、且从某个位置开始之后全都多加了，基本就是这类问题。

6.2 对拍和暴力验证的笨办法

刷模板题时我有一个固定习惯：先写一个暴力版本，专门用来对拍。随机生成 n 很小的数据，比如 n 从 1 到 20，q 到 100，把 BIT 版本的输出和暴力的输出逐行比对。

做法很简单：写一个solution.cpp用 BIT，写一个brute.cpp用暴力，再写一个数据生成器，循环跑。一旦发现问题，就缩小数据规模复现。BIT 的 bug 通常没有太深的过程依赖，都是边界和类型问题，对拍能非常快地定位。

对拍脚本可以用 shell 写一段简单的循环，或者用比赛环境自带的测试工具。我在本地习惯写一个小脚本，随机生成数据后不断比较输出，直到出错为止。这个习惯在打 CF、做 OJ 题时帮了很大的忙。

6.3 什么时候该选 BIT，什么时候选线段树

最后给一张傻瓜式的决策参考：

这里有一个反向经验：很多人习惯一看到区间操作就写线段树，其实很多区间加法加求和的问题用双 BIT 写起来更快。反过来，一看到 BIT 就只会抄单点模板，那遇到区间赋值就完全卡住。工具没有高低，关键是先想清楚操作是否可逆、是否可减。

我刷完 BIT 这一系列题之后最大的体会是：树状数组的所有改动都离不开 lowbit 那条“从叶子到根”、“从节点到前缀”的路径。无论一维、二维、差分、值域二分，本质上都是在问同一个问题——这个下标对应的那一段区间，由哪个节点负责？想清楚这个，代码的每个循环都是水到渠成，而不是背下来的。

最后再分享一个很小的技巧：遇到完全不会的 BIT 变形题，先把暴力做法写出来，然后思考暴力的“查询”能否用一种前缀和优化，暴力的“修改”能否用差分处理。大部分 BIT 题，都逃不出这两招的组合。