基础知识

简介

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

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

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

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

编号方式

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

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

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

令 ，则：

  • 左儿子编号 2 × u，对应区间 [l, mid]；
  • 右儿子编号 2 × u + 1，对应区间 [mid + 1, r]；
  • 父亲编号为 。

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

空间复杂度

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

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

1 + 2 + 4 + ⋯ + 2⌈log n⌉ ≤ 2⌈log n⌉ + 1 一般大小开到 4 × 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 ≠ 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] 没有交集，即 r < L 或 l > R 时，直接返回即可；
  • 如果 [l, r] 被 [L, R] 完全包含，即 l ≥ L 且 r ≤ 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

思路分析

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

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

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

记录一个点的真实值为 w × lzy_mul + lzy_add。

为什么这样记录？
  • 记为 (w + lzy_add) × lzy_mul。此时非常不容易进行更新操作，并且在 lzy_add 变化后，为了消除 Δlzy_add × lzy_mul 的影响，lzy_mul 要对应减小，可能变为小数，精度损失严重。
  • 记为 w × lzy_mul + lzy_add。此时改变 lzy_add 时与 lzy_mul 没有关联，且 lzy_mul 变化后根据分配律 lzy_add × Δlzy_mul 即可。

  • 区间加 x 即得 w × lzy_mul + lzy_add + x，直接将 x 加到加法标记上即可。

  • 区间乘 x 即得 (w × lzy_mul + lzy_add) × x ⇒ w × lzy_mul × x + lzy_add × x，因此要给乘法标记和加法标记都乘上 x。

由于一个点的真实值为 w × lzy_mul + lzy_add，所以：

  1. 原来值为 w；
  2. 下放乘法标记，w ⇒ w × lzy_mul；
  3. 下放加法标记，w × lzy_mul ⇒ w × lzy_mul + lzy_add。

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

时间复杂度：建树 O(n)，q 次操作，每次操作 O(log n)，所以复杂度为 O(n + qlog 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 习题

贪婪大陆