DAY 04
线段树应用
CSP 暑期集训 · Segment Tree Advanced Applications
线段树回顾
建/查/改 核心操作速览
懒标记 Lazy Tag
区间修改 · pushdown 核心机制
双懒标记
区间乘+区间加 · 标记优先级
常见应用
区间最值 · 最大子段和 · 属性速查
| 操作 | 每层访问节点数 | 层数 | 总复杂度 |
|---|---|---|---|
| 单点修改 | 1 | ⌈log₂n⌉ | O(log n) |
| 区间查询 | ≤ 4 | ⌈log₂n⌉ | O(log n) |
| 建树 | n（全部） | ⌈log₂n⌉ | O(n) |
最直接的想法：对 [l, r] 中的每个位置逐一调用单点修改。
初始数组 a = [1, 2, 3, 4, 5, 6, 7, 8]，线段树维护区间和。
查询区间 [3,5] 的和。需要从根节点出发，途中遇到 tag 就 pushdown。
注意：如果节点被查询区间完全覆盖，则直接返回 tree[u]，不需要 pushdown！
ql ≤ l && r ≤ qr，直接 return tree[u]！| 区间查询 | 区间修改（懒标记） | |
| 完全覆盖 | 直接返回 tree[u]，O(1) | 打标记 tree[u]+=v×len, lazy[u]+=v，O(1) |
| 部分覆盖 | pushdown + 递归 | pushdown + 递归 |
| 不覆盖 | 不访问 | 不访问 |
| l, r | 当前递归到的节点所代表的区间范围。例如根节点是 [1, n]，其左儿子是 [1, mid]，右儿子是 [mid+1, n]。 |
| ql, qr | 用户要求的查询/修改的目标区间。在整个递归过程中保持不变。 |
ql <= l && r <= qr → 当前节点 完全被目标区间包含 → ✅ 直接更新/返回，打标记即可y = mul·x + add 这个一次函数
ql <= l && r <= qr 不成立时，| 属性 | 结合律 | 分配律 | 懒标记 | 单位元 |
|---|---|---|---|---|
| 区间和 sum | ✓ | ✓（乘/加均可） | ✓ 区间加/乘 | 0 |
| 区间最值 max/min | ✓ | ✓（区间加） | ✓ 区间加 | -∞ / +∞ |
| 区间 GCD | ✓ | ✗ | 不支持区间加 | 0 |
| sum 线段树 | GCD 线段树 | |
| pushup | tree[u] = tree[2u] + tree[2u+1] | tree[u] = __gcd(tree[2u], tree[2u+1]) |
| 查询初始值 | ans = 0（加法单位元） | ans = 0（gcd单位元：gcd(x,0)=x） |
| 合并操作 | ans += 左 + 右 | ans = __gcd(ans, 左); ans = __gcd(ans, 右) |
| 懒标记 | 支持区间加 | 不支持区间加！（gcd无分配律） |
在数据结构题中，"在线"和"离线"是两种根本不同的处理范式。线段树天然支持在线，但有些场景离线反而更简单。
| 在线处理 | 离线处理 | |
|---|---|---|
| 处理方式 | 每读入一个操作就立即处理并输出，不依赖后续操作 | 先读完所有操作，可以重新排序、分批处理后统一输出 |
| 输入依赖 | 第 i 个操作的输入可能依赖第 i-1 个操作的答案（如加密/解码） | 所有操作一开始就全部已知，无依赖关系 |
| 输出时机 | 处理完一个操作就输出一个答案 | 所有操作处理完后，按原始顺序输出 |
| 典型工具 | 线段树、树状数组、平衡树等动态数据结构 | CDQ分治、整体二分、莫队、分块 |
last_ans 取模后才能得到真实的 l, r"int l = read() % last_ans, r = read() % last_ans;| 对比维度 | 线段树（在线） | CDQ 分治（离线） | 整体二分（离线） |
|---|---|---|---|
| 是否依赖后续操作 | ❌ 不依赖 | ✅ 需要所有操作 | ✅ 需要所有操作 |
| 能否处理强制在线 | ✅ 可以 | ❌ 不行 | ❌ 不行 |
| 典型复杂度 | O(n log n) | O(n log² n) | O(n log n) |
| 实现难度 | 中等 | 较高 | 较高 |
| CSP 出现频率 | ⭐⭐⭐ 高频 | ⭐ 低频 | ⭐ 低频 |
当值域很大（如 10⁹）但操作次数较少时，预分配 4n 空间会爆内存。动态开点线段树通过"用到哪开到哪"解决这个问题。
tree[4 * MAXN]，无论是否用到都占空间const int MAXN = 1e5 + 5; // 操作次数 const int MAXNODE = MAXN * 30; // 最多节点数（操作数 × 树高） struct Node { int ls, rs; // 左右儿子编号（不是 2*u, 2*u+1） int sum; // 维护的信息 } tree[MAXNODE]; int root = 0, cnt = 0; // 根节点编号，节点计数器 // 新建节点 int newNode() { ++cnt; tree[cnt].ls = tree[cnt].rs = tree[cnt].sum = 0; return cnt; } // pushup（和普通线段树一样） void pushup(int u) { tree[u].sum = tree[tree[u].ls].sum + tree[tree[u].rs].sum; } // 单点修改：在值域 [l, r] 的线段树中，给位置 pos 加 v void update(int &u, int l, int r, int pos, int v) { if (!u) u = newNode(); // 如果节点不存在，动态创建 if (l == r) { tree[u].sum += v; return; } int mid = l + (r - l) / 2; if (pos <= mid) update(tree[u].ls, l, mid, pos, v); else update(tree[u].rs, mid + 1, r, pos, v); pushup(u); } // 区间查询 int query(int u, int l, int r, int ql, int qr) { if (!u) return 0; // 节点不存在，返回 0 if (ql <= l && r <= qr) return tree[u].sum; int mid = l + (r - l) / 2, res = 0; if (ql <= mid) res += query(tree[u].ls, l, mid, ql, qr); if (qr > mid) res += query(tree[u].rs, mid + 1, r, ql, qr); return res; }
| 对比维度 | 普通线段树 | 动态开点线段树 |
|---|---|---|
| 节点编号 | u 的左儿子 = 2u，右儿子 = 2u+1 | u 的左儿子 = tree[u].ls，右儿子 = tree[u].rs |
| 空间分配 | 预分配 4n | 用到哪开到哪（最多 m × log n） |
| 适用场景 | 值域 n ≤ 10⁶ | 值域 n ≤ 10⁹，操作次数 m ≤ 10⁵ |
| 代码差异 | 数组开 4 × MAXN | 需要 ls, rs 指针 + newNode 函数 |
| 时间复杂度 | O(log n) | O(log n)（相同） |
#include <bits/stdc++.h> using namespace std; const int MAXN = 5e5 + 5; const int MAXNODE = MAXN * 30; struct Node { int ls, rs, sum; } tree[MAXNODE]; int root = 0, cnt = 0; int newNode() { tree[++cnt] = {0, 0, 0}; return cnt; } void pushup(int u) { tree[u].sum = tree[tree[u].ls].sum + tree[tree[u].rs].sum; } void update(int &u, int l, int r, int pos, int v) { if (!u) u = newNode(); if (l == r) { tree[u].sum += v; return; } int mid = l + (r - l) / 2; if (pos <= mid) update(tree[u].ls, l, mid, pos, v); else update(tree[u].rs, mid + 1, r, pos, v); pushup(u); } int query(int u, int l, int r, int ql, int qr) { if (!u || ql > qr) return 0; if (ql <= l && r <= qr) return tree[u].sum; int mid = l + (r - l) / 2, res = 0; if (ql <= mid) res += query(tree[u].ls, l, mid, ql, qr); if (qr > mid) res += query(tree[u].rs, mid + 1, r, ql, qr); return res; } int a[MAXN]; int main() { int n; scanf("%d", &n); for (int i = 1; i <= n; i++) scanf("%d", &a[i]); long long ans = 0; for (int i = n; i >= 1; i--) { ans += query(root, 1, 1e9, 1, a[i] - 1); // 查询比 a[i] 小的数的个数 update(root, 1, 1e9, a[i], 1); // 插入 a[i] } printf("%lld\n", ans); return 0; }
| 知识点 | 适用场景 | 核心操作 | 时间复杂度 | 关键易错点 |
|---|---|---|---|---|
| 基础线段树 | 单点修改 + 区间查询 | pushup 合并 | O(log n) | 数组4×MAXN |
| 懒标记 | 区间修改 + 区间查询 | pushdown 延迟下传 | O(log n) | 忘记pushdown/pushup |
| 双懒标记 | 区间乘+加 | mul/add标记复合 | O(log n) | mul初始为1,先乘后加 |
| 区间 GCD | GCD 查询 | __gcd 合并 | O(log n · log M) | 不支持区间加，需差分转化 |
| 区间最值 | 最大/最小值 | max/min + lazy | O(log n) | 区间加可直接作用于最值 |
| 扫描线 | 矩形面积并 | 离散化 + 线段树维护覆盖 | O(n log n) | cnt计数，无需pushdown |
线段树不是万能的——不同数据结构有各自的"甜点区"。
| 数据结构 | 核心能力 | 时间 | 空间 | 在线/离线 | 实现难度 |
|---|---|---|---|---|---|
| 树状数组 | 单点加 + 前缀和 | O(log n) | O(n) | 在线 | ⭐ 极简 |
| 线段树 | 区间修改 + 区间查询（sum/max/min/gcd） | O(log n) | O(n) | 在线 | ⭐⭐ 中等 |
| ST 表 | 静态 RMQ（无修改） | 查询 O(1) | O(n log n) | 在线 | ⭐⭐ 中等 |
| 分块 | 区间操作（万能但慢） | O(√n) | O(n) | 在线 | ⭐ 简单 |
| FHQ Treap | 区间翻转、分裂合并（文艺平衡树） | O(log n) | O(n) | 在线 | ⭐⭐⭐ 较难 |
| 李超线段树 | 维护直线/线段集合，查询最大/最小值 | O(log n) | O(n) | 在线 | ⭐⭐⭐ 较难 |
| 莫队 | 区间查询（无修改） | O(n√n) | O(n) | 离线 | ⭐⭐ 中等 |
| CDQ 分治 | 多维偏序问题 | O(n log² n) | O(n) | 离线 | ⭐⭐⭐ 较难 |
| 变体 | 核心思想 | 解决什么问题 | 典型题目 |
|---|---|---|---|
| 动态开点线段树 | 不预分配 4n 空间，用到哪开到哪 | 值域很大（如 10⁹）但操作次数少 | P1908 逆序对（值域 10⁹） P3369 普通平衡树 |
| 可持久化线段树 （主席树） |
每次修改生成新版本，保留历史版本 | 区间第 k 小、可持久化数据结构 | P3834 主席树 P3919 可持久化数组 |
| 李超线段树 | 维护直线集合，查询某 x 处的最值 | 直线/线段覆盖问题 | P4097 [SDOI2013] 线段 P4254 Blue Mary 开公司 |
| 线段树合并 | 两棵线段树对应节点合并 | 树上问题（如子树信息合并） | P4556 线段树合并 P3605 升序数 |
| 标记永久化 | 懒标记不下传，查询时累加 | 避免 pushdown 的常数，适合可持久化 | P3373 线段树 3（标记永久化优化） |
| 编号 | 题目 | 知识点 | 难度 |
|---|---|---|---|
| 1 | P3372 【模板】线段树 1 | 区间加 + 区间和（懒标记基础模板） | 普及+/提高− |
| 2 | P3374 【模板】树状数组 1 | 单点加 + 区间和（树状数组对比） | 普及+/提高− |
| 3 | P1816 忠诚 | 区间最小值（RMQ 线段树/ST表） | 普及 |
| 4 | P1198 [JSOI2008] 最大数 | 线段树 + 动态插入 + 区间最大值 | 普及+/提高− |
| 5 | P1531 I Hate It | 单点修改 + 区间最大值 | 普及+/提高− |
| 6 | P3373 【模板】线段树 2 | 双懒标记（乘法+加法） | 普及+/提高− |
| 7 | P2023 [AHOI2009] 维护序列 | 双懒标记（P3373 双倍经验） | 普及+/提高− |
| 8 | P1253 扶苏的问题 | 区间赋值 + 区间加 + 区间最大值 | 普及+/提高− |
| 9 | P1890 gcd区间 | 区间 GCD 查询（线段树/ST表） | 普及 |
| 10 | P1558 色板游戏 | 区间赋值 + 位运算（颜色压缩） | 普及+/提高− |
| 11 | P1438 无聊的数列 | 差分 + 线段树（区间修改转化） | 普及+/提高− |
| 12 | P4145 上帝造题的七分钟 2 | 区间开方 + 区间求和（势能分析） | 提高 |
| 13 | P4513 小白逛公园 | 区间最大子段和（维护4个值） | 提高 |
| 14 | P5490 【模板】扫描线 | 扫描线 + 线段树（矩形面积并） | 提高 |