本课时有配套视频讲解，购买后即可观看（永久有效）
线段树1
一、课上练习
编程练习
- 线段树1：L49967
二、知识总结
✨ 核心思想
线段树（Segment Tree）是一种二叉树形数据结构，每个节点维护一个区间的信息。它支持 O(log n) 的单点修改和区间查询，是竞赛中最重要、最通用的数据结构之一。
线段树的核心思想是分治：将区间不断二分，每个节点代表一个子区间，通过合并子区间信息来回答查询。
✨ 算法原理
树的结构
对于长度为 n 的数组，线段树是一棵近似完全二叉树：
- 根节点（编号 1）维护区间
[1, n] - 节点 p 维护区间
[l, r]，其两个子节点：- 左子节点
2*p维护[l, mid] - 右子节点
2*p+1维护[mid+1, r] - 其中
mid = (l + r) / 2
- 左子节点
建树
从根节点开始递归：叶子节点直接赋值，非叶子节点由两个子节点合并得到。
单点修改
从根节点递归找到目标叶子节点，修改后回溯更新沿途所有祖先节点。
区间查询
递归时判断查询区间与当前节点区间的关系：
- 完全包含 → 直接返回当前节点的值
- 部分重叠 → 递归查询左右子节点并合并
- 完全不交 → 返回零元素
✨ 代码实现
线段树 - 单点修改 + 区间求和/求最值
1#include <bits/stdc++.h>
2using namespace std;
3
4const int MAXN = 200005;
5
6int a[MAXN];
7int n, m;
8
9struct SegTree {
10 int sum[MAXN * 4]; // 区间和
11 int mx[MAXN * 4]; // 区间最大值
12 int mn[MAXN * 4]; // 区间最小值
13
14 // 用子节点信息更新当前节点
15 void pushUp(int p) {
16 sum[p] = sum[p * 2] + sum[p * 2 + 1];
17 mx[p] = max(mx[p * 2], mx[p * 2 + 1]);
18 mn[p] = min(mn[p * 2], mn[p * 2 + 1]);
19 }
20
21 // 建树：节点p维护区间[l, r]
22 void build(int p, int l, int r) {
23 if (l == r) {
24 sum[p] = mx[p] = mn[p] = a[l];
25 return;
26 }
27 int mid = (l + r) / 2;
28 build(p * 2, l, mid);
29 build(p * 2 + 1, mid + 1, r);
30 pushUp(p);
31 }
32
33 // 单点修改：将a[x]改为val
34 void update(int p, int l, int r, int x, int val) {
35 if (l == r) {
36 sum[p] = mx[p] = mn[p] = val;
37 return;
38 }
39 int mid = (l + r) / 2;
40 if (x <= mid) update(p * 2, l, mid, x, val);
41 else update(p * 2 + 1, mid + 1, r, x, val);
42 pushUp(p);
43 }
44
45 // 区间查询：求[ql, qr]的和
46 int querySum(int p, int l, int r, int ql, int qr) {
47 if (ql <= l && r <= qr) return sum[p]; // 完全包含
48 int mid = (l + r) / 2;
49 int res = 0;
50 if (ql <= mid) res += querySum(p * 2, l, mid, ql, qr);
51 if (qr > mid) res += querySum(p * 2 + 1, mid + 1, r, ql, qr);
52 return res;
53 }
54
55 // 区间查询：求[ql, qr]的最大值
56 int queryMax(int p, int l, int r, int ql, int qr) {
57 if (ql <= l && r <= qr) return mx[p];
58 int mid = (l + r) / 2;
59 int res = INT_MIN;
60 if (ql <= mid) res = max(res, queryMax(p * 2, l, mid, ql, qr));
61 if (qr > mid) res = max(res, queryMax(p * 2 + 1, mid + 1, r, ql, qr));
62 return res;
63 }
64
65 // 区间查询：求[ql, qr]的最小值
66 int queryMin(int p, int l, int r, int ql, int qr) {
67 if (ql <= l && r <= qr) return mn[p];
68 int mid = (l + r) / 2;
69 int res = INT_MAX;
70 if (ql <= mid) res = min(res, queryMin(p * 2, l, mid, ql, qr));
71 if (qr > mid) res = min(res, queryMin(p * 2 + 1, mid + 1, r, ql, qr));
72 return res;
73 }
74} seg;
75
76int main() {
77 ios::sync_with_stdio(false);
78 cin.tie(nullptr);
79
80 cin >> n >> m;
81 for (int i = 1; i <= n; i++) cin >> a[i];
82
83 seg.build(1, 1, n);
84
85 while (m--) {
86 int op;
87 cin >> op;
88 if (op == 1) {
89 // 单点修改
90 int x, val;
91 cin >> x >> val;
92 seg.update(1, 1, n, x, val);
93 } else {
94 // 区间求和
95 int l, r;
96 cin >> l >> r;
97 cout << seg.querySum(1, 1, n, l, r) << "\n";
98 }
99 }
100
101 return 0;
102}✨ 执行示例
以数组 a = [2, 5, 1, 4, 3]（n=5）为例：
建树后的线段树结构（以区间和为例）：
1[1,5]=15
2 / \
3 [1,3]=8 [4,5]=7
4 / \ / \
5 [1,2]=7 [3,3]=1 [4,4]=4 [5,5]=3
6 / \
7[1,1]=2 [2,2]=5查询 querySum(1, 1, 5, 2, 4)：
- 节点[1,5]：[2,4] 部分重叠，递归左右
- 节点[1,3]：[2,4] 部分重叠，递归左右
- 节点[1,2]：[2,4] 部分重叠，递归右子
- 节点[2,2]：[2,4] 完全包含 → 返回 5
- 节点[3,3]：[2,4] 完全包含 → 返回 1
- 节点[4,5]：[2,4] 部分重叠，递归左子
- 节点[4,4]：[2,4] 完全包含 → 返回 4
- 结果 = 5 + 1 + 4 = 10 ✓
单点修改 update(1, 1, 5, 3, 6) — 将 a[3] 改为 6：
- 递归到叶子 [3,3]，修改为 6
- 回溯更新 [1,3] = 2+5+6 = 13
- 回溯更新 [1,5] = 13+7 = 20
✨ 解题步骤详解
- 确定维护信息：根据题目需求决定每个节点存什么（和、最值、计数等）。
- 定义 pushUp：如何用子节点信息合并出父节点信息，这是线段树的核心。
- 确定修改方式：单点修改直接递归到叶子。
- 确定查询方式：区间查询时注意零元素的选择（加法用 0，最大值用 INT_MIN 等）。
为什么数组开 4 倍？
线段树用数组存储，编号为 p 的节点的子节点编号为 2p 和 2p+1。最坏情况下，n 个叶子的线段树最多需要 4n 个节点的空间。
线段树节点信息合并的例子
| 维护信息 | pushUp 逻辑 | 查询零元素 |
|---|---|---|
| 区间和 | sum[p] = sum[ls] + sum[rs] | 0 |
| 区间最大值 | mx[p] = max(mx[ls], mx[rs]) | INT_MIN |
| 区间最小值 | mn[p] = min(mn[ls], mn[rs]) | INT_MAX |
| 区间 GCD | g[p] = gcd(g[ls], g[rs]) | 0 |
✨ 常见错误
- 数组空间不足：线段树数组必须开 4 倍 大小，否则运行时越界。
- pushUp 忘写或位置错：每次修改后必须回溯调用 pushUp 更新祖先。
- 递归边界写错：
if (l == r)是叶子节点的判定，不要忘记。 - 查询时零元素选错：求最大值时初始值应为 INT_MIN 而非 0。
- 左右子节点编号写错：左子是
2p，右子是2p+1，不要搞反。 - mid 的划分不一致：建树、修改、查询三个函数中 mid 的计算方式必须相同。
✨ 算法评价
| 指标 | 复杂度 |
|---|---|
| 建树时间 | O(n) |
| 单点修改 | O(log n) |
| 区间查询 | O(log n) |
| 空间复杂度 | O(n)（实际开 4n） |
优点：
- 功能强大，几乎能维护任何可合并信息
- 支持多种修改和查询操作
- 扩展性极强（懒标记、可持久化等）
缺点：
- 代码量较大，常数比树状数组大
- 空间是原数组的 4 倍
适用场景：几乎所有需要区间操作的场景。线段树是竞赛选手的核心武器。
三、课后练习
编程练习
- 查单词：L49945