Day 14-plus 学生讲义：树状数组——从动态前缀和到逆序对

前置知识：前缀和、差分、二进制基础、排序与二分。

本课是 Day14 后的独立拓展内容，原 Day14 图论/DSU 模拟卷不变。全篇数组使用 1 下标。

今天要解决一类反复出现的问题：

数组会修改，但还要快速查询前缀或区间；
扫描序列时，要快速统计已经出现了多少个更小值或更大值。

1. 学习路线

顺序	内容	学完要能做到
1	lowbit 与管辖区间	看懂 tree[x] 保存哪一段
2	单点增加、前缀查询	默写 add/query
3	单点修改、区间求和	写出基础完整模板
4	差分树状数组	区间增加、单点查询
5	两棵树状数组	区间增加、区间求和
6	离散化与逆序对	统计左边更大或更小的个数
7	CF61E 三元组贡献	枚举中间位置，左右两边相乘
8	树状数组上二分	找动态频率中的第 k 个

2. 为什么普通前缀和会卡住

静态数组的区间和可以写成：

$$\operatorname{sum}(l,r)=s[r]-s[l-1].$$

但若 a[x] 增加 d，所有 s[x..n] 都要跟着增加 d。一次修改最坏是 O(n)。

方法	修改一个数	查询区间和
直接数组	O(1)	O(n)
普通前缀和	O(n)	O(1)
树状数组	O(log n)

树状数组不保存每一个完整前缀，而是保存若干段长度为 1、2、4、8……的小区间和。查询时拼起来，修改时只更新包含该位置的区间。

3. lowbit 是什么

lowbit(x) 表示 x 的二进制最低位 1 对应的数值：

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

x	二进制	lowbit(x)
3	0011	1
4	0100	4
6	0110	2
8	1000	8
12	1100	4

先自算：

• lowbit(10)=?
• lowbit(16)=?
• lowbit(20)=?

答案分别是 2、16、4。

注意：lowbit(0)=0。若 add 从下标 0 开始，x+=lowbit(x) 永远不动，会死循环。

4. tree[x] 保存哪一段

定义：

$$tree[x]=a[x-lowbit(x)+1]+\cdots+a[x].$$

所以 tree[x] 管辖：

$$[x-lowbit(x)+1,x].$$

n=8 时：

x	tree[x] 管辖区间
1	[1,1]
2	[1,2]
3	[3,3]
4	[1,4]
5	[5,5]
6	[5,6]
7	[7,7]
8	[1,8]

例如：

• tree[6] 保存 a[5]+a[6]；
• tree[4] 保存 a[1]+a[2]+a[3]+a[4]；
• tree[7] 只保存 a[7]。

这里的 tree 不是一棵用指针连接的树，而是把树形关系压在数组下标的二进制中。

5. 单点增加：add

若 a[x] 增加 d，所有管辖范围包含 x 的节点都要增加 d：

void add(int x, long long d)
{
	for (; x <= n; x += lowbit(x))
		tree[x] += d;
}

当 n=8，执行 add(3,5)：

tree[3] += 5
tree[4] += 5
tree[8] += 5

路径：3 -> 4 -> 8

为什么是向上加 lowbit(x)？因为要跳到下一个包含当前位置的更大管辖区间。

再手算：

• add(5,d) 的路径：5 -> 6 -> 8；
• add(6,d) 的路径：6 -> 8；
• add(8,d) 的路径：8。

6. 前缀查询：query

query(x) 返回前缀 a[1]+...+a[x]：

long long query(int x)
{
	long long res = 0;
	for (; x > 0; x -= lowbit(x))
		res += tree[x];
	return res;
}

手算 query(6)：

tree[6] 保存 [5,6]
tree[4] 保存 [1,4]

[1,6] = [5,6] + [1,4]
路径：6 -> 4 -> 0

手算 query(7)：

[1,7] = tree[7] + tree[6] + tree[4]
路径：7 -> 6 -> 4 -> 0

每次减去 lowbit(x)，就是把已经统计的最后一段删掉。

区间和仍然是两个前缀之差：

long long rangeQuery(int l, int r)
{
	return query(r) - query(l - 1);
}

7. 基础完整模板

操作：

• 1 x d：a[x] 增加 d；
• 2 l r：查询 [l,r] 的和。

#include<bits/stdc++.h>
using namespace std;

#define ll long long
const int N = 2e5 + 10;

int n, q;
ll tree[N];

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

void add(int x, ll d)
{
	for (; x <= n; x += lowbit(x))
		tree[x] += d;
}

ll query(int x)
{
	ll res = 0;
	for (; x > 0; x -= lowbit(x))
		res += tree[x];
	return res;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> n >> q;
	for (int i = 1; i <= n; i++)
	{
		ll x;
		cin >> x;
		add(i, x);
	}

	while (q--)
	{
		int op;
		cin >> op;
		if (op == 1)
		{
			int x;
			ll d;
			cin >> x >> d;
			add(x, d);
		}
		else
		{
			int l, r;
			cin >> l >> r;
			cout << query(r) - query(l - 1) << '\n';
		}
	}
	return 0;
}

复杂度：

• 初始化：O(nlog n)；
• 每次修改：O(log n)；
• 每次查询：O(log n)；
• 空间：O(n)。

7.1 题目若说“改成”怎么办

add(x,d) 是“增加 d”。若题目要求把 a[x] 改成 v：

long long d = v - a[x];
a[x] = v;
add(x, d);

不要把“改成 10”写成“再加 10”。

8. 差分树状数组：区间加、单点查

若操作是：

• [l,r] 全部增加 d；
• 查询 a[x]。

普通差分的区间修改为：

diff[l] += d;
diff[r + 1] -= d;

原数组单点值是差分前缀和，因此让树状数组维护 diff：

void rangeAdd(int l, int r, long long d)
{
	add(l, d);
	if (r + 1 <= n) add(r + 1, -d);
}

long long pointQuery(int x)
{
	return query(x);
}

例子：

对 [2,5] 加 3
diff[2] += 3
diff[6] -= 3

query(1) 不包含 +3
query(2..5) 包含 +3
query(6) 又被 -3 抵消

本质不是树状数组突然会修改区间，而是差分把一次区间修改变成了两次单点修改。

9. 两棵树状数组：区间加、区间和

差分数组记为 d：

$$a[i]=\sum_{j=1}^{i}d[j].$$

原数组的前缀和为：

$$\begin{aligned} \sum_{i=1}^{x}a[i] &=\sum_{j=1}^{x}(x-j+1)d[j]\\ &=(x+1)\sum_{j=1}^{x}d[j]-\sum_{j=1}^{x}j\cdot d[j]. \end{aligned}$$

所以：

• 第一棵树维护 d[j]；
• 第二棵树维护 j*d[j]。

核心代码：

long long t1[N], t2[N];

void add(long long tree[], int x, long long d)
{
	for (; x <= n; x += lowbit(x))
		tree[x] += d;
}

long long query(long long tree[], int x)
{
	long long res = 0;
	for (; x > 0; x -= lowbit(x))
		res += tree[x];
	return res;
}

void change(int x, long long d)
{
	add(t1, x, d);
	add(t2, x, 1ll * x * d);
}

void rangeAdd(int l, int r, long long d)
{
	change(l, d);
	if (r + 1 <= n) change(r + 1, -d);
}

long long prefix(int x)
{
	return 1ll * (x + 1) * query(t1, x) - query(t2, x);
}

long long rangeQuery(int l, int r)
{
	return prefix(r) - prefix(l - 1);
}

这部分不要只背代码。必须知道两棵树分别维护什么，否则公式中的 x、x+1、i 很容易写混。

10. 离散化

若数组值达到 10^9，不能开十亿大小的树状数组。但统计大小关系时，只需要保留排名。

原值: [100, -5, 20, 20]
排序去重: [-5, 20, 100]
排名: [3, 1, 2, 2]

标准写法：

vector<int> b;
for (int i = 1; i <= n; i++) b.push_back(a[i]);
sort(b.begin(), b.end());
b.erase(unique(b.begin(), b.end()), b.end());

for (int i = 1; i <= n; i++)
	rnk[i] = lower_bound(b.begin(), b.end(), a[i]) - b.begin() + 1;

为什么要 +1？因为树状数组不能从下标 0 更新。

离散化只保留大小关系。排名 3 与排名 1 的差是 2，并不代表原值相差 2。

11. 什么时候优先想到树状数组

适合：

• 单点修改、区间求和；
• 区间增加、单点查询；
• 区间增加、区间求和；
• 扫描过程中统计已出现元素的大小关系；
• 逆序对、顺序对、三元组贡献；
• 动态频率中的第 k 个。

基础树状数组不擅长：

• 区间赋值；
• 任意修改下的区间最值；
• 需要复杂懒标记的区间操作。

这些问题通常要改模型或使用线段树。

12. 易错点清单

• 下标必须从 1 开始，不能 add(0,d)。
• query(0)=0，所以 query(l-1) 在 l=1 时没有问题。
• 求和、逆序对和三元组答案优先用 long long。
• “增加”与“改成”不同，赋值要计算差值。
• 区间差分修改注意 r+1 是否越界。
• 离散化更新排名，不更新原值。
• 严格与非严格只差一个等号，要先写清统计条件。
• 多组数据和多遍扫描都要清空树状数组。
• CF61E 两个计数相乘前转成 long long。
• 第 k 个查询要求频率非负。

13. 总结

tree[x] 管辖结尾在 x、长度为 lowbit(x) 的区间。
单点修改向上跳，前缀查询向下跳。
区间和等于两个前缀和相减。
区间修改先想差分，区间和进阶用两棵树。
值域太大先离散化，排名必须从 1 开始。
统计大小关系先分清严格与非严格。
二元关系一遍统计，三元组枚举中点算两边贡献。