①核心要点与万能模板
| 知识板块 | 必须记住的核心 | 复杂度 |
|---|
| lowbit | x & -x，取最低位的 1（x 必须 > 0） | O(1) |
| c[i] 管辖 | 覆盖 (i−lowbit(i), i]，长度 lowbit(i) | — |
| update / add | for (; i <= n; i += lowbit(i)) c[i] += v; | O(log n) |
| query / sum | for (s=0; i; i -= lowbit(i)) s += c[i]; | O(log n) |
| 区间和 | sum(r) − sum(l−1) | O(log n) |
| O(n) 建树 | c[i] += a[i]; j = i+lowbit(i); c[j] += c[i]; | O(n) |
| 区间加+单点查 | BIT 维护差分，add(l,v); add(r+1,−v); | O(log n) |
| 区间加+区间和 | 双 BIT：(x+1)·Σd − Σj·d | O(log n) |
| 逆序对 | 离散化 + ans += (i−1) − query(rk[i]) | O(n log n) |
| 第 k 小 | BIT 上倍增二分 | O(log n) |
C++万能模板 · 树状数组全家桶（背下来）
const int MAXN = 500005;
long long c[MAXN], t1[MAXN], t2[MAXN];
int n;
inline int lowbit(int x) { return x & (-x); }
/* ========== ① 基础：单点加 + 前缀和 ========== */
void add(int i, long long v) {
for (; i <= n; i += lowbit(i)) c[i] += v;
}
long long sum(int i) {
long long s = 0;
for (; i > 0; i -= lowbit(i)) s += c[i];
return s;
}
/* ========== ② 区间加 + 单点查（c 存差分） ========== */
void rangeAddPoint(int l, int r, long long v) {
add(l, v); add(r + 1, -v); // 数组开到 n+2
}
long long pointQuery(int x) { return sum(x); }
/* ========== ③ 区间加 + 区间和（双 BIT） ========== */
void add2(long long t[], int i, long long v) {
for (; i <= n; i += lowbit(i)) t[i] += v;
}
long long sum2(long long t[], int i) {
long long s = 0;
for (; i > 0; i -= lowbit(i)) s += t[i];
return s;
}
void rangeAdd(int l, int r, long long v) {
add2(t1, l, v); add2(t1, r + 1, -v);
add2(t2, l, 1LL*l*v); add2(t2, r + 1, -1LL*(r+1)*v);
}
long long prefSum(int x) { return 1LL*(x+1)*sum2(t1,x) - sum2(t2,x); }
long long rangeSum(int l, int r) { return prefSum(r) - prefSum(l - 1); }
/* ========== ④ O(n) 建树 ========== */
void build(int a[]) {
for (int i = 1; i <= n; i++) {
c[i] += a[i];
int j = i + lowbit(i);
if (j <= n) c[j] += c[i];
}
}
/* ========== ⑤ 求全局第 k 小（BIT 上倍增） ========== */
int kth(int k) {
int pos = 0;
for (int pw = 1 << 20; pw; pw >>= 1) {
if (pos + pw <= n && c[pos + pw] < k) {
pos += pw;
k -= c[pos];
}
}
return pos + 1;
}
②拓展案例
拓1树状数组求全局第 k 小（BIT 上倍增）
题意：维护一个可重集合，支持插入数 x、删除数 x、查询第 k 小的数。值域 ≤ 106，操作数 ≤ 105。
思路：用一个 BIT 记每个值的出现次数。query(v) = 值 ≤ v 的元素总数。
找第 k 小：从高位到低位尝试「把当前位设为 1」，如果跳过去之后 c[pos+pw] < k，说明第 k 小在更右边，就跳过去并把 k 减去跳过的元素数。最后 pos + 1 就是答案。
这本质上是在 BIT 结构上做二分：因为 c 的区间是嵌套的，所以可以按二进制位逐步逼近。复杂度 O(log n)，比"二分 + 前缀和 O(log²n)"更快。
C++动态第 k 小
int M = 1 << 20; // 二进制上界（>= 值域）
int c[MAXM];
void insert(int x, int d) { for (; x <= M; x += lowbit(x)) c[x] += d; }
int kth(int k) { // 返回第 k 小的值
int pos = 0;
for (int pw = M; pw; pw >>= 1) {
if (c[pos + pw] < k) { pos += pw; k -= c[pos]; }
}
return pos + 1;
}
运行结果
操作: 插入 3, 1, 4, 1, 5
集合 = {1, 1, 3, 4, 5}
第 1 小 = 1
第 2 小 = 1
第 3 小 = 3
第 5 小 = 5
删除一个 1 → 集合 = {1, 3, 4, 5}
第 2 小 = 3
拓2二维树状数组（子矩阵和）
题意：n×m 矩阵，支持单点加、子矩阵求和。n, m ≤ 1000，操作 ≤ 105。
思路：把一维 BIT 推广到二维——c[i][j] 同时沿两个方向管辖。update 时两层循环都要做 lowbit 跳跃，query 时两层循环都要做 lowbit 下降，复杂度 O(log²n)。
子矩阵 (x1,y1)-(x2,y2) 的和用容斥：sum(x2,y2) − sum(x1−1,y2) − sum(x2,y1−1) + sum(x1−1,y1−1)。
C++二维树状数组
int N, M, c[1024][1024];
void add(int x, int y, int v) {
for (int i = x; i <= N; i += lowbit(i))
for (int j = y; j <= M; j += lowbit(j))
c[i][j] += v;
}
int sum(int x, int y) {
int s = 0;
for (int i = x; i > 0; i -= lowbit(i))
for (int j = y; j > 0; j -= lowbit(j))
s += c[i][j];
return s;
}
int 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);
}
运行结果
3×3 矩阵初始全 0
操作: add(1,1,5), add(2,2,3), add(3,3,7)
查询 (1,1)-(2,2) → 5 + 3 = 8
查询 (2,2)-(3,3) → 3 + 7 = 10
查询 (1,1)-(3,3) → 15
空间: 1024×1024×4B ≈ 4MB，安全。
注意: 复杂度的 log 是"两次"，即 O(log N · log M)。
拓3树状数组 + 扫描线（矩形面积并的计数思想）
题意：给出 n 个矩形，求它们的面积并。n ≤ 105。
核心思想（扫描线）：把所有矩形的上下边按 y 排序，用一条水平线从下往上扫描。线上每个位置 x 有一个"被覆盖次数" cnt[x]。
· 遇到矩形下边 → 对应 x 区间的 cnt 加 1；遇到上边 → 减 1。
· 相邻两条边之间的面积 = (y₂ − y₁) × (cnt > 0 的 x 总长度)。
树状数组能否胜任？「区间加 + 查询全局"值大于 0"的位置长度」——可惜这个信息不可减（cnt 从 1 变 0 需要知道是不是真的没有覆盖），所以标准做法是线段树 + 扫描线（维护 min 与 min 的个数）。
但是如果问题简化为「求被至少一个矩形覆盖的格子数」（离散坐标、单点计数），那么用"二维差分 + 树状数组"或"扫描线 + BIT 单点加区间和"就能胜任。
此处引入扫描线的意义：它是"把二维问题化为一维区间操作"的通用范式，下一讲的线段树会给出完整实现。
C++扫描线思路（BIT 可解版：离散坐标覆盖计数）
// 事件：(y, x1, x2, delta) 下边 delta=+1，上边 delta=-1
struct Ev { int y, x1, x2, d; };
sort(ev, ev + 2 * n, [](const Ev&a, const Ev&b){ return a.y < b.y; });
long long area = 0;
for (int i = 0; i < 2 * n; i++) {
if (i) area += 1LL * (ev[i].y - ev[i-1].y) * coveredLength();
rangeAdd(ev[i].x1, ev[i].x2, ev[i].d); // 差分 BIT 维护覆盖次数
}
// coveredLength()：cnt[x] > 0 的位置数（本题不可直接用 BIT，需线段树）
为什么这里要用线段树？因为「cnt[x] > 0 的总长度」这个量在区间加之后无法从子区间的同种信息中合并出来（从"cnt=1"减到"cnt=0"时，父区间不知道还有没有别的覆盖）。这类"不可减信息 + 区间修改"必须请线段树出场——这正是下一讲的主题。