本课时有配套视频讲解，购买后即可观看（永久有效）
线段树3
一、课上练习
编程练习
- 线段树3：L49940
二、知识总结
✨ 核心思想
进阶线段树涵盖多种高级技巧：
- 多重懒标记：当线段树同时支持区间乘法和区间加法时，需要维护两个标记并注意下传顺序。
- 线段树 Beats（吉司机线段树）：支持区间取 min/max 操作，通过维护最值及次值信息实现高效更新。
- 可持久化线段树（主席树）：保留历史版本，通过共享节点实现空间高效的版本管理。
✨ 算法原理
一、多重懒标记
当同时支持"区间乘 mul"和"区间加 add"时，定义操作顺序为先乘后加：
节点实际值 = 原值 × mul + add
下传规则：父节点标记 (mulp, addp) 传给子节点 (mulc, addc)：
mul_c = mul_c * mul_p
add_c = add_c * mul_p + add_p二、线段树 Beats
问题：给定数组，支持区间对 x 取 min（即 a[i] = min(a[i], x)）和区间求和。
关键维护信息：
mx：区间最大值cnt：最大值出现次数se：区间严格次大值
更新策略：对于 chmin(l, r, x) 操作：
- 若
x >= mx：无需操作 - 若
se < x < mx：仅最大值被影响，sum 减少(mx - x) * cnt - 若
x <= se：无法快速处理，递归到子节点
这保证了均摊 O(n log^2 n) 的复杂度。
三、可持久化线段树（主席树）
核心思想：每次修改不改变原节点，而是创建新节点。由于每次修改只影响 O(log n) 个节点，新旧版本可以共享大量节点。
应用：查询区间第 k 小值（对值域建线段树，每加入一个元素创建新版本）。
✨ 代码实现
多重懒标记线段树
线段树 - 区间乘法 + 区间加法
1#include <bits/stdc++.h>
2using namespace std;
3
4const int MAXN = 100005;
5typedef long long ll;
6
7int n, m;
8ll MOD;
9ll a[MAXN];
10
11struct SegTree {
12 ll sum[MAXN * 4];
13 ll mulTag[MAXN * 4]; // 乘法标记
14 ll addTag[MAXN * 4]; // 加法标记
15 int sz[MAXN * 4];
16
17 void pushUp(int p) {
18 sum[p] = (sum[p * 2] + sum[p * 2 + 1]) % MOD;
19 }
20
21 // 打标记：先乘mul再加add
22 void applyTag(int p, ll mul, ll add) {
23 sum[p] = (sum[p] * mul % MOD + add * sz[p] % MOD) % MOD;
24 mulTag[p] = mulTag[p] * mul % MOD;
25 addTag[p] = (addTag[p] * mul % MOD + add) % MOD;
26 }
27
28 void pushDown(int p) {
29 if (mulTag[p] != 1 || addTag[p] != 0) {
30 applyTag(p * 2, mulTag[p], addTag[p]);
31 applyTag(p * 2 + 1, mulTag[p], addTag[p]);
32 mulTag[p] = 1;
33 addTag[p] = 0;
34 }
35 }
36
37 void build(int p, int l, int r) {
38 mulTag[p] = 1;
39 addTag[p] = 0;
40 sz[p] = r - l + 1;
41 if (l == r) {
42 sum[p] = a[l] % MOD;
43 return;
44 }
45 int mid = (l + r) / 2;
46 build(p * 2, l, mid);
47 build(p * 2 + 1, mid + 1, r);
48 pushUp(p);
49 }
50
51 // 区间乘法
52 void multiply(int p, int l, int r, int ql, int qr, ll val) {
53 if (ql <= l && r <= qr) {
54 applyTag(p, val, 0);
55 return;
56 }
57 pushDown(p);
58 int mid = (l + r) / 2;
59 if (ql <= mid) multiply(p * 2, l, mid, ql, qr, val);
60 if (qr > mid) multiply(p * 2 + 1, mid + 1, r, ql, qr, val);
61 pushUp(p);
62 }
63
64 // 区间加法
65 void add(int p, int l, int r, int ql, int qr, ll val) {
66 if (ql <= l && r <= qr) {
67 applyTag(p, 1, val);
68 return;
69 }
70 pushDown(p);
71 int mid = (l + r) / 2;
72 if (ql <= mid) add(p * 2, l, mid, ql, qr, val);
73 if (qr > mid) add(p * 2 + 1, mid + 1, r, ql, qr, val);
74 pushUp(p);
75 }
76
77 ll query(int p, int l, int r, int ql, int qr) {
78 if (ql <= l && r <= qr) return sum[p];
79 pushDown(p);
80 int mid = (l + r) / 2;
81 ll res = 0;
82 if (ql <= mid) res = (res + query(p * 2, l, mid, ql, qr)) % MOD;
83 if (qr > mid) res = (res + query(p * 2 + 1, mid + 1, r, ql, qr)) % MOD;
84 return res;
85 }
86} seg;可持久化线段树（主席树）
主席树 - 区间第k小值
1#include <bits/stdc++.h>
2using namespace std;
3
4const int MAXN = 200005;
5const int MAXM = MAXN * 20; // 每次修改最多新建log个节点
6
7// 动态开点，不用数组编号的2*p方式
8int ls[MAXM], rs[MAXM], cnt[MAXM];
9int root[MAXN]; // 每个版本的根节点
10int tot = 0; // 节点计数器
11
12int a[MAXN], b[MAXN]; // 原数组和离散化数组
13int n, m;
14
15// 建空树
16int build(int l, int r) {
17 int p = ++tot;
18 cnt[p] = 0;
19 if (l == r) return p;
20 int mid = (l + r) / 2;
21 ls[p] = build(l, mid);
22 rs[p] = build(mid + 1, r);
23 return p;
24}
25
26// 在prev版本的基础上，在位置x插入一个元素，返回新版本根节点
27int update(int prev, int l, int r, int x) {
28 int p = ++tot;
29 ls[p] = ls[prev];
30 rs[p] = rs[prev];
31 cnt[p] = cnt[prev] + 1;
32 if (l == r) return p;
33 int mid = (l + r) / 2;
34 if (x <= mid) ls[p] = update(ls[prev], l, mid, x);
35 else rs[p] = update(rs[prev], mid + 1, r, x);
36 return p;
37}
38
39// 查询区间[ql, qr]中的第k小
40// 利用版本差：root[qr] - root[ql-1]得到区间信息
41int query(int u, int v, int l, int r, int k) {
42 if (l == r) return l;
43 int mid = (l + r) / 2;
44 int leftCnt = cnt[ls[v]] - cnt[ls[u]]; // 左子树中的元素个数
45 if (k <= leftCnt) return query(ls[u], ls[v], l, mid, k);
46 else return query(rs[u], rs[v], mid + 1, r, k - leftCnt);
47}
48
49int main() {
50 ios::sync_with_stdio(false);
51 cin.tie(nullptr);
52
53 cin >> n >> m;
54 for (int i = 1; i <= n; i++) {
55 cin >> a[i];
56 b[i] = a[i];
57 }
58
59 // 离散化
60 sort(b + 1, b + n + 1);
61 int len = unique(b + 1, b + n + 1) - b - 1;
62
63 // 建空树作为版本0
64 root[0] = build(1, len);
65
66 // 依次插入每个元素，创建版本1~n
67 for (int i = 1; i <= n; i++) {
68 int pos = lower_bound(b + 1, b + len + 1, a[i]) - b;
69 root[i] = update(root[i - 1], 1, len, pos);
70 }
71
72 // 查询
73 while (m--) {
74 int l, r, k;
75 cin >> l >> r >> k;
76 int pos = query(root[l - 1], root[r], 1, len, k);
77 cout << b[pos] << "\n";
78 }
79
80 return 0;
81}✨ 执行示例
主席树查询第 k 小
数组 a = [5, 2, 1, 4, 3]，离散化后 b = [1, 2, 3, 4, 5]。
查询区间 [2, 4] 的第 2 小值：
对应元素为 {2, 1, 4}，排序后为 {1, 2, 4}，第 2 小 = 2。
使用版本差 root[4] - root[1]：
- 左子树（值域[1,3]）元素个数 = cnt[ls[root[4]]] - cnt[ls[root[1]]] = 3 - 1 = 2
k=2 <= 2，递归左子树- 左子树的左子（值域[1,2]）元素个数 = 2 - 1 = 1
- k=2 > 1，递归右子，k = 2 - 1 = 1
- 到达叶子节点，对应值域位置 2，即 b[2] = 2
结果 = 2 ✓
✨ 解题步骤详解
多重懒标记的设计步骤
- 确定所有操作类型（加法、乘法、赋值等）
- 确定标记的合并顺序（先乘后加是最常见的）
- 推导 pushDown 时的标记合并公式
- 验证：连续多次操作的标记合并是否正确
主席树的关键技巧
- 动态开点：不用 2p/2p+1 方式，改用
ls[p]/rs[p]存储子节点编号 - 版本差：
root[r]的信息减去root[l-1]的信息 = 区间[l, r]的信息 - 空间估算：n 个版本，每个版本新增 O(log n) 个节点，总空间 O(n log n)
✨ 常见错误
- 多重标记下传顺序错误：必须先乘后加，
addc = addc * mulp + addp。 - 主席树空间开小：一般需要
n 20到n 40个节点。 - 主席树修改时改了旧节点：update 必须创建新节点，不能修改原节点。
- 离散化后忘记用离散化后的值：插入和查询都应该使用离散化后的坐标。
- 取模不完整：多重标记涉及多次乘加运算，每步都要取模。
✨ 算法评价
| 数据结构 | 修改 | 查询 | 空间 | 适用场景 |
|---|---|---|---|---|
| 多重懒标记线段树 | O(log n) | O(log n) | O(n) | 区间乘+加+求和 |
| 线段树 Beats | 均摊 O(log^2 n) | O(log n) | O(n) | 区间取 min/max + 求和 |
| 主席树 | O(log n) | O(log n) | O(n log n) | 区间第 k 小、历史版本查询 |
进阶线段树是信息学竞赛中区分选手水平的关键技能，掌握这些技巧能解决大量高难度题目。
三、课后练习
编程练习
- 开关：L49943