线段树

基础知识

简介

线段树是一颗不那么完全的二叉树。

设线段树有 $h$ 层，则第 $1\sim h-1$ 层是满的，而第 $h$ 层并不一定是满的，而是由第 $h-1$ 层的非叶子节点伸出两个儿子。

• 维护区间序列信息；
• 所有非叶子节点都有两个儿子
• 树上每个节点对应序列的一个区间

线段树是算法竞赛中常见的用来维护 区间信息 的数据结构。

编号方式

线段树是将序列分治的过程，并且将分治的过程记录下来。

根节点编号为 $1$，对应整个区间 $[1,n]$。

对于当前节点编号 $u$，对应区间 $[l, r]$。

令 $mid=\lfloor\dfrac{l+r}{2}\rfloor$，则：

• 左儿子编号 $2\times u$，对应区间 $[l,mid]$；
• 右儿子编号 $2\times u+1$，对应区间 $[mid+1,r]$；
• 父亲编号为 $\lfloor\dfrac{x}{2}\rfloor$。

区间长度为 $1$ 的线段树节点为叶子节点，没有左右儿子。

空间复杂度

线段树是一个类似完全二叉树的结构，开空间时要为下面一层留足空间

考虑从上至下的每层节点数量之和，得到

$$ 1+2+4+\cdots+2^{\lceil\log n\rceil}\le2^{\lceil\log n\rceil+1} $$

一般大小开到 $4\times n$ 即可。

基本知识中，$n$ 为区间长度的数量级。

更新

从子树更新信息返回时，我们需要合并子树所计算的信息。

什么时候需要调用呢？

• 询问时，我们没有修改子树的值，无需调用。
• 修改时，我们修改了子树的值，所有需要调用。

pushup() 的设计比较灵活，需要根据题目具体分析设计。

接下来的基本知识中，我们以区间求和与区间加上一个值来说明。

1
2
3
4
5

void pushup(int u) {
	w[u] = merge(w[u * 2], w[u * 2 + 1]);
  // merge 是合并两个值的方法
  // 可能还需要维护其它的值
}

建树

我们令 w 数组存储其区间的所有数字之和。

• 当 $l=r$ 即区间长度为 $1$ 时，结束递归，赋值 w[u] = a[l]。
• 当 $l\not=r$ 即区间长度大于 $1$ 时，拆分为 $[l,mid]$ 和 $[r,mid]$ 两段，分别递归，最后合并。

建树时每个节点都只会被访问一次，时间复杂度 $O(n)$。

1
2
3
4
5
6
7
8
9
10

void build(int u, int l, int r) {
	if (l == r) {
		w[u] = a[l];
		return ;
	}
	int mid = l + r >> 1;
	build(u * 2, l, mid);
	build(u * 2 + 1, mid + 1, r);
	pushup(u); // 更新完子树后需要合并
}

单点操作

单点查询

晚点写。

单点修改

晚点写。

区间操作

区间定位

如何定位需要的区间？

假设当前递归到的区间为 $[l,r]$，目标区间为 $[L,R]$，那么要分类讨论：

• 如果 $[l,r]$ 与 $[L,R]$ 没有交集，即 $rR$ 时，直接返回即可；
• 如果 $[l,r]$ 被 $[L,R]$ 完全包含，即 $l\ge L$ 且 $r\le R$ 时，由于已经使用 w 记录了，直接返回存储的值即可；
• 否则，将其拆分为 $[l,mid]$ 和 $[mid+1,r]$ 两部分，分别进行递归。

如图，$[2,2],[3,4],[5,7]$ 就是我们需要的区间。

故我们需要两个判断区间关系的函数：

1
2
3
4
5
6
7
8

// 当前递归到的区间为 [l,r]，目标区间为 [L,R]，后面代码中均用这个意义
bool inRange(int l, int r, int L, int R) { // 是否被完全包含
	return l >= L && r <= R;
}

bool outRange(int l, int r, int L, int R) { // 是否没有交集
	return R < l || L > r;
}

区间查询

按照区间定位找到每一个需要的区间，将其值累加返回即可。

复杂度证明

在区间查询中，并不是每一层只会向下延申一个节点，而是对左右节点分别递归。在线段树每层的递归中，最多只有两个节点会向下继续递归，也就是被查询区间两端点所在的节点。而剩下的节点要么被完全包含，要么与查询区间无交。因此，每一层只会新建两个递归函数。而因为树高为 $\log n$，所以时间复杂度为 $O(\log n)$。

区间修改

如果对于每一个区间中的叶子节点进行操作，然后逐渐合并回到根节点时，访问的数量与节点总数量同级，时间复杂度为 $O(n)$，较劣。如何优化呢？

晚点写。

题目分析

线段树 - 题单 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

提高 1 例题

【模板】线段树 1

就是基础知识的分析了。代码见上面的分析。

【模板】线段树 2

思路分析

由于题目中出现了两种操作：$\times,+$，所以我们需要多个懒标记。

记 w 表示区间和，lzy_add 表示加法的懒标记，lzy_mul 表示乘法的懒标记。

• lzy_add 初始化为 $0$，因为开始时没有需要添加的数。
• lzy_mul 初始化为 $1$，因为对于一个数 $x$，有 $x=1\times x$，所以乘的值默认为 $1$。此外，由于更新 lzy_mul 时是 (lzy_mul[u] *= x) %= m，如果初始为 $0$ 的话需要进行特判，比较麻烦。

记录一个点的真实值为 $\texttt{w}\times\texttt{lzy\_mul}+\texttt{lzy\_add}$。

为什么这样记录？

• 记为 $(\texttt{w}+\texttt{lzy\_add})\times\texttt{lzy\_mul}$。此时非常不容易进行更新操作，并且在 lzy_add 变化后，为了消除 $\Delta\texttt{lzy\_add}\times\texttt{lzy\_mul}$ 的影响，lzy_mul 要对应减小，可能变为小数，精度损失严重。
• 记为 $\texttt{w}\times\texttt{lzy\_mul}+\texttt{lzy\_add}$。此时改变 lzy_add 时与 lzy_mul 没有关联，且 lzy_mul 变化后根据分配律 $\texttt{lzy\_add}\times\Delta\texttt{lzy\_mul}$ 即可。

• 区间加 $x$ 即得 $\texttt{w}\times\texttt{lzy\_mul}+\texttt{lzy\_add}+x$，直接将 $x$ 加到加法标记上即可。

• 区间乘 $x$ 即得 $(\texttt{w}\times\texttt{lzy\_mul}+\texttt{lzy\_add})\times x⇒\texttt{w}\times\texttt{lzy\_mul}\times x+\texttt{lzy\_add}\times x$，因此要给乘法标记和加法标记都乘上 $x$。

由于一个点的真实值为 $\texttt{w}\times\texttt{lzy\_mul}+\texttt{lzy\_add}$，所以：

1. 原来值为 $\texttt{w}$；
2. 下放乘法标记，$\texttt{w}⇒\texttt{w}\times\texttt{lzy\_mul}$；
3. 下放加法标记，$\texttt{w}\times\texttt{lzy\_mul}⇒\texttt{w}\times\texttt{lzy\_mul}+\texttt{lzy\_add}$。

由此可知，下方标记时先下放乘法标记，再下方加法标记。

时间复杂度：建树 $O(n)$，$q$ 次操作，每次操作 $O(\log n)$，所以复杂度为 $O(n+q\log n)$。

核心代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

// build() 遍历到每一个节点时也要 lzy_mul[u] = 1;
// 要开 long long，这里 #define int long long 了
void maketag(int u, int l, int r, int x, int type) { // type：1 乘 2 加
	if (type == 1) {
		(lzy_mul[u] *= x) %= m;
		(lzy_add[u] *= x) %= m;
		(w[u] *= x) %= m;
	} else {
		(lzy_add[u] += x) %= m;
		(w[u] += (r - l + 1) * x) %= m;
	}
}

void pushdown(int u, int l, int r) {
	int mid = l + r >> 1;
  // 先下放乘法标记，再下放加法标记
	maketag(u * 2, l, mid, lzy_mul[u], 1);
	maketag(u * 2, l, mid, lzy_add[u], 2);
	maketag(u * 2 + 1, mid + 1, r, lzy_mul[u], 1);
	maketag(u * 2 + 1, mid + 1, r, lzy_add[u], 2);
	lzy_add[u] = 0, lzy_mul[u] = 1; // 重置
}

signed main() {
	std::cin.tie(0)->sync_with_stdio(0);
	std::cin >> n >> q >> m;
	for (int i = 1; i <= n; ++i) std::cin >> a[i];
	build(1, 1, n);
	for (int op, x, y, k; q; --q) {
		std::cin >> op >> x >> y;
		if (op == 3) std::cout << query(1, 1, n, x, y) << '\n';
		else std::cin >> k, update(1, 1, n, x, y, k % m, op);
    // 重点：此处要 k % m，否则在信友队上 k 达到了 1e18，可能会爆 long long，取模后就没有这样的问题了。
    // 此外，maketag() 中的 type 设计简化了代码，与 op 相同
	}
	std::cout.flush();
	return 0;
}

【CSP-S 2022】 策略游戏

小白逛公园

提高 1 习题

贪婪大陆