📘线段树

2026-08-04
⭐⭐⭐ GESP 8级

📖概念讲解

线段树是一棵完全二叉树，用于高效处理区间查询和单点/区间更新操作。核心思想：把区间拆成若干段，每段维护一个聚合值（如区间和、最值）。

⚡ 易混淆：线段树 ≠ 树状数组。树状数组只能做前缀查询+单点更新，线段树能处理区间更新+区间查询，功能更强但代码更长。

💻代码示例

1#include <iostream>
2using namespace std;
3
4int a[100005], tree[400005]; // tree: 线段树数组，开4倍大小
5
6// 建树：当前节点node管区间[l,r]
7void build(int node, int l, int r) {
8 if (l == r) {
9 tree[node] = a[l]; // 叶子节点直接存原数组值
10 return;
11 }
12 int mid = (l + r) / 2; // 中点，左右分治
13 build(node * 2, l, mid); // 左孩子管 [l, mid]
14 build(node * 2 + 1, mid + 1, r); // 右孩子管 [mid+1, r]
15 tree[node] = tree[node * 2] + tree[node * 2 + 1]; // 父节点 = 左+右（区间和）
16}
17
18// 单点更新：把位置pos的值改成val
19void update(int node, int l, int r, int pos, int val) {
20 if (l == r) {
21 tree[node] = val; // 到达叶子，直接赋值
22 return;
23 }
24 int mid = (l + r) / 2;
25 if (pos <= mid) update(node * 2, l, mid, pos, val); // 在左半边
26 else update(node * 2 + 1, mid + 1, r, pos, val); // 在右半边
27 tree[node] = tree[node * 2] + tree[node * 2 + 1]; // 回溯时更新父节点
28}
29
30// 区间查询：查询[ql, qr]的和
31int query(int node, int l, int r, int ql, int qr) {
32 if (ql <= l && r <= qr) return tree[node]; // 当前区间完全在查询范围内
33 int mid = (l + r) / 2, sum = 0;
34 if (ql <= mid) sum += query(node * 2, l, mid, ql, qr); // 左半有交集
35 if (qr > mid) sum += query(node * 2 + 1, mid + 1, r, ql, qr); // 右半有交集
36 return sum;
37}
38
39int main() {
40 int n = 5;
41 for (int i = 1; i <= n; i++) a[i] = i * 10; // 原数组: 10,20,30,40,50
42 build(1, 1, n); // 从根节点1开始建树
43 cout << query(1, 1, n, 2, 4) << endl; // 查 [2,4] 的和
44 update(1, 1, n, 3, 100); // 把位置3改成100
45 cout << query(1, 1, n, 2, 4) << endl; // 再查 [2,4] 的和
46 // 输出: 90（即20+30+40）
47 // 输出: 160（即20+100+40）
48 return 0;
49}

🧩互动小测

Q1：线段树数组通常需要开多大？

Q2：线段树查询区间 [2,5] 时，节点管 [1,8]，mid=4。接下来应该怎么递归？

Q3：线段树单点更新后需要做什么？

🏋️动手练一练

📝 编程练习

给定一个长度为 n 的数组，有 q 个操作：
1 l r：查询区间 [l, r] 的最大值
2 pos val：把位置 pos 的值改为 val

要求：用线段树实现，查询最大值而不是区间和。
提示：把 tree[node] 存的值从"区间和"改成"区间最大值"，build/update/query 逻辑类似，只需把"+"改成 max()。
参考答案： 
#include <iostream>
#include <algorithm>
using namespace std;

int a[100005], tree[400005];

void build(int node, int l, int r) {
    if (l == r) { tree[node] = a[l]; return; }
    int mid = (l + r) / 2;
    build(node*2, l, mid);
    build(node*2+1, mid+1, r);
    tree[node] = max(tree[node*2], tree[node*2+1]); // 改成max
}

void update(int node, int l, int r, int pos, int val) {
    if (l == r) { tree[node] = val; return; }
    int mid = (l + r) / 2;
    if (pos <= mid) update(node*2, l, mid, pos, val);
    else update(node*2+1, mid+1, r, pos, val);
    tree[node] = max(tree[node*2], tree[node*2+1]);
}

int query(int node, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) return tree[node];
    int mid = (l + r) / 2, res = -1e9;
    if (ql <= mid) res = max(res, query(node*2, l, mid, ql, qr));
    if (qr > mid) res = max(res, query(node*2+1, mid+1, r, ql, qr));
    return res;
}

要点：核心就是把区间和的"求和"操作替换成"取最大值"，初始值设为极小值 -1e9 即可。其余递归结构完全一样。

📝易错点提醒

🏠 返回主页
← 2026-08-03 2026-08-04 2026-08-05 →
学完这个知识点后点一下