树状数组(BIT) 知识点讲解

概念

想象你在玩一个“数数游戏”。桌上有一排编号从 1 到 $n$ 的盒子，每个盒子里放了一些糖果。现在有两个请求：

1. 往第 $x$ 号盒子里增加 $v$ 颗糖果；

2. 问前 $y$ 号盒子（$1 \sim y$）里一共有多少颗糖果。

如果 $n, m$ 都只有 100，你可以每次把前 $y$ 个盒子一个个数一遍，总复杂度 $O(n \cdot m)$，勉强能过。但如果 $n, m$ 涨到 $10^5$，每次数一遍就要扫 $10^5$ 个数，总共要扫 $10^{10}$ 次，直接超时。

有没有一种数据结构，能让“单点加”和“前缀和”都变成对数级 $O(\log n)$？有，就是树状数组（Fenwick Tree，简称 BIT）。它代码极短，只靠几个简单的循环就能实现这两个操作，是线段树之前最值得先吃透的 $O(\log n)$ 结构。

触发清单（看到这些信号第一时间想到本知识点）

定义

术语翻译： - 前缀和：数组前 $x$ 个数的累加值，即 $a[1]+a[2]+\dots+a[x]$。 - 差分数组：令 $d[i]=a[i]-a[i-1]$（约定 $a[0]=0$），则 $a[x]$ 等于差分数组的前缀和。 - lowbit(x)：取出 $x$ 二进制表示中最低位的 1及其后面的 0 组成的数值。例如 $12=1100_2$，lowbit(12)=4=100_2。

核心：lowbit 为什么能取出最低位的 1

设 $x$ 最低位的 1 在第 $k$ 位（从右数 0 起），则 $x$ 的低 $k$ 位全为 0、第 $k$ 位为 1。

• ~x（按位取反）：低 $k$ 位全变 1，第 $k$ 位变 0。
• -x = ~x + 1：低 $k$ 位「全是 1 再加 1」会一路进位到第 $k$ 位，使第 $k$ 位变回 1、低 $k$ 位归 0。
• 于是 -x 只有第 $k$ 位是 1，其余位恰好与 $x$ 相反。
• x & -x 里，只有第 $k$ 位两者都是 1、其余位至少一个是 0 → 结果 = $2^k$ = 最低位那个 1 的值。✓

举例 $x=12=1100_2$：~x=0011，-x=0100，1100 & 0100 = 0100_2 = 4。

大纲还给出另一种等价写法（用异或）：

lowbit(i) = i & (i ^ (i - 1)) （与 i & -i 完全等价）

• x & (x ^ (x - 1)) 靠 x ^ (x-1)「把最低位的 1 及其右边的 0 全变成 1、左边全 0」，再与 x 相与，同样只留下最低位的 1。

CCF 大纲的正式定义（提高级考纲原文）

对数组 $a$ 构造数组 $c$，其中

c[i] = a[i - 2^k + 1] + … + a[i]（$k$ 为 $i$ 在二进制下末尾 0 的个数），即从 $a[i - 2^k + 1]$ 到 $a[i]$ 的累加和；数组 $c$ 称为 $a$ 的树状数组。

等价的写法是 c[i] = a[i - lowbit(i) + 1] + … + a[i]，其中 lowbit(i) 是 $i$ 二进制最低位的 1 及其后面的 0 组成的数值。换句话说，c[i] 管的区间长度恰好是 lowbit(i)、左端点是 i - lowbit(i) + 1——这正是上面「每个 c[i] 管自己一段」说法的官方表述，也是 query/add 不断 ±lowbit 能不重不漏拼出前缀和的根本原因。

两个操作（全课就这俩函数）

① 单点加 add(pos, val) —— 从 pos 起每次 pos += lowbit(pos) 往「父节点」走，把路径上的 c 都加上 val：

void add(int pos, int val) {
 for (; pos <= n; pos += lowbit(pos)) c[pos] += val;
}

② 前缀和 query(x) —— 从 x 起每次 x -= lowbit(x) 往「左兄弟」走，把路径上的 c 累加：

int query(int x) {
 int s = 0;
 for (; x > 0; x -= lowbit(x)) s += c[x];
 return s;
}

区间和 [l, r] = query(r) - query(l - 1)。

c[i] 管理的区间：长度 = lowbit(i)，左端点 = i - lowbit(i) + 1，右端点 = i。两个操作每次去掉/加上一个二进制位的 1，步数 = x 二进制中 1 的个数，故都是 $O(\log n)$。

为什么这些写法是对的（推演）

推演 0 · lowbit 为什么能取出最低位的 1（补码逐位走查）：见上文。

推演 1 · 单点改 + 区间和为什么是 O(log n)：

c[i] 管长度 lowbit(i)、以 i 结尾的一段。a[k]+=v 时，从 i=k 起 i += lowbit(i) 更新所有覆盖 k 的节点；sum(R) 时从 i=R 起 i -= lowbit(i) 累加。两者每次砍掉/补上一个二进制位的 1，步数 = 二进制中 1 的个数 ≤ ⌊log₂n⌋+1，故 $O(\log n)$。下标必须从 1 起（lowbit(0)=0 会让 x -= lowbit(x) 卡在 0 死循环）。

推演 2 · 区间加 + 单点查为什么是「差分数组的 BIT」：

区间 [l,r] += v 等价于差分 d[l]+=v, d[r+1]-=v；单点 a[x] = 差分数组前缀和 = query(x)。于是「区间加」变成两次 add，「单点查」变成一次 query——完全套模板 1，只是维护的对象换成差分数组。

推演 3 · 逆序对为什么用 BIT：

从左到右把 a[i] 的值当下标 +1，每次查「已插入中 > a[i] 的有几个」= query(MAX) - query(a[i])，即 a[i] 贡献的逆序对；累计即总数，$O(n \log n)$。本质是"边插入边查前缀和"，BIT 正是干这个的。

技巧速查表（背下来）

原讲义配图

例题

例题 1：单点修改 + 区间求和（自构造）

① 题目描述

给定一个长度为 $n$ 的数组 $a$（下标从 1 开始）。接下来有 $m$ 次操作，每次操作给出三个整数 $op, x, y$：

• 若 $op = 1$，表示把 $a[x]$ 增加 $y$；
• 若 $op = 2$，表示询问 $a[x \dots y]$ 的和。

数据范围：$n, m \le 5 \times 10^5$，$a_i, y$ 为整数。请输出每次询问的结果。

② 审题分析

• 读题抓条件：单点修改、区间求和、$n,m$ 很大。
• 定需求：需要一种结构支持 $O(\log n)$ 的单点加和前缀和。
• 为什么能用本知识点：这正是树状数组模板 1 的主场。
• 如果不用会怎样：用暴力前缀和每次 $O(n)$，总复杂度 $O(nm) \approx 2.5 \times 10^{11}$，必超时。

③ 解题思路

1. 读入 $n, m$。

2. 读入初始数组 $a$，用 $n$ 次 add(i, a[i]) 建树。

3. 循环处理 $m$ 次操作：

- $op=1$：调用 add(x, y)。

- $op=2$：输出 query(y) - query(x - 1)。

④ C++ 完整参考代码（逐行注释）

#include <cstdio>
int n, m, c[500005]; // c 就是树状数组本身：c[i] 管「以 i 结尾、长 lowbit(i)」的一段

int lowbit(int x) { return x & -x; } // 取出 x 二进制最低位的 1：12(1100₂) → 4(100₂)

void add(int pos, int val) { // 单点加：把 a[pos] 加 val
 for (; pos <= n; pos += lowbit(pos)) // 沿「父节点」一路向上，直到跳出数组
 c[pos] += val; // 路径上每个 c[pos] 都管着这个位置，全都要 +val
}

int query(int x) { // 前缀和：返回 a[1] + a[2] + … + a[x]
 int s = 0;
 for (; x > 0; x -= lowbit(x)) // 每次剥掉 x 最低位的 1，直到 x = 0
 s += c[x]; // 拼上的这些 c[x] 段刚好不重不漏盖住 a[1..x]
 return s;
}

int main() {
 scanf("%d%d", &n, &m);
 for (int i = 1; i <= n; i++) { // 下标必须从 1 开始！lowbit(0)=0 会让 query 死循环
 int v; scanf("%d", &v);
 add(i, v); // 建树 = 逐个单点加，n 次 add 就位
 }
 while (m--) {
 int op, x, y; scanf("%d%d%d", &op, &x, &y);
 if (op == 1) add(x, y); // 操作 1：a[x] += y
 else printf("%d\n", query(y) - query(x - 1)); // 操作 2：区间和 = 两个前缀相减
 }
 return 0;
}

⑤ 代码解读（含真实运行输出）

设输入如下（$n=8, m=4$）：

8 4
1 2 3 4 5 6 7 8
1 3 5
2 4 7
2 1 8
1 8 -2

• 初始数组 $a = [1,2,3,4,5,6,7,8]$。
• 操作 1：add(3,5) → $a$ 变为 $[1,2,8,4,5,6,7,8]$。
• 操作 2：query(7)-query(3) → $a[4..7]$ 的和 = $4+5+6+7 = 22$。
• 操作 3：query(8)-query(0) → 总和 = $1+2+8+4+5+6+7+8 = 41$。
• 操作 4：add(8,-2) → $a$ 变为 $[1,2,8,4,5,6,7,6]$。

真实运行结果（按顺序输出）：

22
41

（注：题目只要求输出询问结果，因此只有两行。）

例题 2：区间修改 + 单点查询（自构造）

① 题目描述

给定长度为 $n$ 的数组 $a$（下标从 1 开始）。接下来有 $m$ 次操作，每次操作给出三个整数 $op, x, y$：

• 若 $op = 1$，表示把区间 $a[x \dots y]$ 全部增加 $y$；
• 若 $op = 2$，表示询问 $a[x]$ 当前的值。

数据范围：$n, m \le 2 \times 10^5$，$a_i, y$ 为整数。请输出每次询问的结果。

② 审题分析

• 读题抓条件：区间加、单点查、$n,m$ 较大。
• 定需求：需要 $O(\log n)$ 的区间加和单点查。
• 为什么能用本知识点：这是树状数组模板 2 的经典场景，利用差分数组把区间加转化为两次单点加。
• 如果不用会怎样：直接在区间上循环 add 会退化成 $O(n)$ 单次操作，总复杂度 $O(nm)$ 超时。

③ 解题思路

1. 读入 $n, m$。

2. 读入初始数组 $a$，用差分建树：对每个 $i$ 执行 add(i, a[i] - a[i-1])（约定 $a[0]=0$）。

3. 循环处理 $m$ 次操作：

- $op=1$：add(x, y); add(y+1, -y);

- $op=2$：输出 query(x)。

④ C++ 完整参考代码（逐行注释）

#include <cstdio>
int n, m, c[200005]; // c 是差分数组的树状数组，开 n+2 防越界

int lowbit(int x) { return x & -x; }

void add(int pos, int val) {
 for (; pos <= n + 1; pos += lowbit(pos)) c[pos] += val;
}

int query(int x) {
 int s = 0;
 for (; x > 0; x -= lowbit(x)) s += c[x];
 return s;
}

int main() {
 scanf("%d%d", &n, &m);
 int prev = 0;
 for (int i = 1; i <= n; i++) {
 int v; scanf("%d", &v);
 add(i, v - prev); // 差分建树：d[i] = a[i] - a[i-1]
 prev = v;
 }
 while (m--) {
 int op, x, y; scanf("%d%d%d", &op, &x, &y);
 if (op == 1) {
 add(x, y); // d[x] += y
 add(y + 1, -y); // d[y+1] -= y
 } else {
 printf("%d\n", query(x)); // a[x] = 差分数组前缀和
 }
 }
 return 0;
}

⑤ 代码解读（含真实运行输出）

设输入如下（$n=5, m=3$）：

5 3
1 2 3 4 5
1 2 10
2 3
2 5

• 初始 $a = [1,2,3,4,5]$，差分数组 $d = [1,1,1,1,1,0]$。
• 操作 1：区间 $[2,3]$ 加 $10$ → $a$ 变为 $[1,12,13,4,5]$。
• 操作 2：查 $a[3]$ → $13$。
• 操作 3：查 $a[5]$ → $5$。

真实运行结果：

13
5

例题复盘总结

两道题的共同点与差异：

• 共性特征：都是“数组 + 多次修改 + 多次查询”，且 $n,m$ 较大，暴力必超时。
• 各自技巧：

- 例题 1：单点改 + 区间查 → 直接套模板 1 的 add/query。

- 例题 2：区间改 + 单点查 → 差分转单点，再套模板 1。

• 审题模板（固定思考流程）：

1. 识别操作类型（单点/区间、修改/查询）。

2. 判断是否需要差分（区间改 + 单点查）。

3. 确认下标从 1 开始，r+1 可能越界需开 n+2。

4. 写出 add/query 框架，填入具体逻辑。

• 错误清单（上文未讲过的特有错误）：

- 例题 2 中忘记开 n+2，导致 add(y+1, -y) 越界段错误。

- 例题 2 中差分建树时写成 add(i, a[i]) 而非 add(i, a[i]-a[i-1])，导致所有查询结果偏大。

- 例题 1 中区间和写成 query(r)-query(l) 少减 1，漏掉左端点。

- 例题 2 中区间加时只对 d[l] 加 v 而忘记对 d[r+1] 减 v，导致修改效果只影响左半部分。

写法总表

分工说明：触发清单告诉你“什么时候想到本知识点”，速查表告诉你“具体怎么写”，总表则按难度从细到粗列出所有技法层次。

常见错误

1. 下标从 0 开始导致死循环：query(0) 时 x -= lowbit(x) 永远是 0，循环条件 x>0 不成立直接返回 0，但 add(0, v) 会让 pos += lowbit(pos) 卡在 0 无限循环。所有下标必须从 1 计数，输入为 0 时要 +1 或特判。

2. 区间和写成 query(r) - query(l)：少减了 1，左端点被漏算。正确写法是 query(r) - query(l - 1)。

3. 模板 2 忘记用差分：直接在区间 [l,r] 上循环 add 会退化成 $O(n)$ 单次操作，$m$ 次操作直接超时。区间改必须转 d[l]+=k, d[r+1]-=k 再查前缀和。

4. 数值当下标时没离散化：a[i] 可能是 $10^9$ 或负数，c[10^9] 数组开不下。先把数值排序去重映射成 $1..m$。

5. 数组 c 开太小 / 没清零：模板 1 开 n+1，模板 2 开 n+2；多组数据之间要 memset 或重新 add。

自测

1. 写出 lowbit(x) 的两种写法（用 &，以及用异或的等价写法 x & (x ^ (x - 1))）。并口头说清 x & -x 为什么能留下最低位的 1（用补码推一遍）。

2. 模板 1 里 add 和 query 的循环方向分别是什么？为什么是 $O(\log n)$？

3. 区间 [l, r] 求和为什么是 query(r) - query(l-1)？如果写成 query(r) - query(l) 会少算什么？

4. 「区间加 k，单点查 a[x]」为什么要用差分数组转成模板 1？直接在 [l,r] 上 add 会怎样？

5. 用树状数组求逆序对时，查询语句应该写在插入之前还是之后？为什么要离散化？

举一反三 · 审题流水线

拿到一道数组题，按这条流水线走一遍：

• 第一步：数数有多少次“改”、多少次“查”，分别是什么类型（单点/区间）。
• 第二步：看数据范围，$n,m$ 是否大到 $O(nm)$ 会超时。
• 第三步：匹配触发清单——单点改 + 区间查？区间改 + 单点查？逆序对？偏序？
• 第四步：确定下标含义——是位置当下标，还是数值当下标？后者记得先离散化。
• 第五步：写两个核心函数 add/query 的框架，把边界条件（pos <= n, x > 0, r+1 越界）补上。
• 第六步：套进题目逻辑，先过样例，再考虑多组数据清零。

练手题

题 A：给定长度为 $n$ 的数组 $a$，接下来 $m$ 次操作：

• $1\ x\ v$：把 $a[x]$ 增加 $v$；
• $2\ x\ y$：把区间 $a[x \dots y]$ 全部增加 $y$；
• $3\ x$：询问 $a[x]$ 的值。

请输出所有 $3$ 次操作的结果。数据范围 $n,m \le 1.5 \times 10^5$。

题 B：有 $n$ 个位置，每个位置有一个初始值 $a_i$。接下来 $m$ 次操作：

• $1\ l\ r\ v$：把区间 $a[l \dots r]$ 全部增加 $v$；
• $2\ x$：询问 $a[x]$ 的值。

请输出所有 $2$ 次操作的结果。数据范围 $n,m \le 2 \times 10^5$。