线段树入门到会用：一篇讲清写法

发表于 更新于 阅读次数：
线段树的原理、建树、单点/区间修改、区间查询的完整写法

为什么需要线段树

给你一个数组，要求支持两种操作：

  1. 修改某个元素（或者某段区间）
  2. 查询某段区间的和 / 最大值 / 最小值

朴素做法：修改 $O(1)$，查询 $O(n)$。前缀和做法：查询 $O(1)$，修改 $O(n)$。两种都怕”修改和查询都很多”的场景。

线段树把两种操作都做到 $O(\log n)$，代价是 $O(n)$ 的空间和 $O(n \log n)$ 的建树时间。

核心思想

线段树是一棵二叉树，每个节点负责数组的一段区间 $[l, r]$：

  • 根节点负责 $[1, n]$
  • 每个节点把负责的区间对半分给两个儿子
  • 叶子节点负责单个元素 $[i, i]$

对于节点编号的技巧：如果节点 $p$ 负责一段区间，那么：

  • 左儿子编号 $2p$，右儿子编号 $2p+1$（位运算写法：p << 1 和 p << 1 | 1）
  • 中点 $mid = \lfloor (l+r)/2 \rfloor$，左儿子管 $[l, mid]$，右儿子管 $[mid+1, r]$

用 1 号点作根、2p 编号时，开 4n 的数组空间一定够。

以数组 [1, 3, 5, 7, 9, 11] 为例，区间和线段树长这样：

1
2
3
4
5
6
7
                [1,6] sum=36
               /            \
        [1,3] sum=9       [4,6] sum=27
        /      \           /       \
   [1,2]=4   [3,3]=5   [4,5]=16   [6,6]=11
    /    \              /     \
[1,1]=1 [2,2]=3    [4,4]=7  [5,5]=9

建树：递归分治

维护区间和的例子。叶子直接赋值，非叶子节点 = 左儿子 + 右儿子：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
const int N = 1e5 + 5;
long long sum[N << 2];
int a[N];

void pushup(int p) {              // 由儿子更新父亲
    sum[p] = sum[p << 1] + sum[p << 1 | 1];
}

void build(int p, int l, int r) {
    if (l == r) { sum[p] = a[l]; return; }  // 叶子
    int mid = (l + r) >> 1;
    build(p << 1, l, mid);
    build(p << 1 | 1, mid + 1, r);
    pushup(p);
}
// 调用：build(1, 1, n);

三行核心逻辑：叶子赋值、递归两边、合并上来。几乎所有线段树操作都是这个骨架。

单点修改

从根出发，看目标位置在左半还是右半，一路走到叶子，改完再沿路 pushup：

1
2
3
4
5
6
7
void update(int p, int l, int r, int x, int v) {
    if (l == r) { sum[p] = v; return; }     // 找到叶子
    int mid = (l + r) >> 1;
    if (x <= mid) update(p << 1, l, mid, x, v);
    else          update(p << 1 | 1, mid + 1, r, x, v);
    pushup(p);                              // 回溯时更新祖先
}

复杂度：树高 $O(\log n)$，每层只走一个儿子。

区间查询

查询 $[ql, qr]$ 的和，从根出发，三种情况：

  • 当前区间与查询区间无交集：返回 0（对 sum 来说的”单位元”）
  • 当前区间完全被包含在查询区间内：直接返回 sum[p]，不再往下
  • 部分相交：拆成左右儿子各查一半，加起来
1
2
3
4
5
6
7
long long query(int p, int l, int r, int ql, int qr) {
    if (qr < l || r < ql) return 0;         // 无交集
    if (ql <= l && r <= qr) return sum[p];  // 完全包含
    int mid = (l + r) >> 1;
    return query(p << 1, l, mid, ql, qr)
         + query(p << 1 | 1, mid + 1, r, ql, qr);
}

每层最多访问 4 个节点，所以复杂度也是 $O(\log n)$。

到这里，单点修改 + 区间查询的线段树已经完整了。洛谷 P3374（单点修改区间和）可以直接过。

进阶：区间修改 + 懒标记

如果要把 $[ql, qr]$ 整段加 $v$，逐个单点修改是 $O(n \log n)$，等于白学。解决办法是懒标记（lazy tag）。

核心想法：修改整个区间时，先在能”完全覆盖”的节点上记账（打标记），告诉它”你管的所有数都加过 v 了”，但不下传给儿子——等以后真的需要访问儿子时再传。

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
long long sum[N << 2], tag[N << 2];   // tag: 该节点整段尚未下传的加法标记

void pushdown(int p, int l, int r) {  // 把标记传给两个儿子
    if (!tag[p]) return;
    int mid = (l + r) >> 1;
    int ls = p << 1, rs = p << 1 | 1;
    tag[ls] += tag[p];
    sum[ls] += tag[p] * (mid - l + 1);        // 左儿子区间长度
    tag[rs] += tag[p];
    sum[rs] += tag[p] * (r - mid);
    tag[p] = 0;
}

void update(int p, int l, int r, int ql, int qr, long long v) {
    if (qr < l || r < ql) return;
    if (ql <= l && r <= qr) {          // 完全覆盖：记账即走
        sum[p] += v * (r - l + 1);
        tag[p] += v;
        return;
    }
    pushdown(p, l, r);                 // 要访问儿子了，先还账
    int mid = (l + r) >> 1;
    update(p << 1, l, mid, ql, qr, v);
    update(p << 1 | 1, mid + 1, r, ql, qr, v);
    pushup(p);
}

long long query(int p, int l, int r, int ql, int qr) {
    if (qr < l || r < ql) return 0;
    if (ql <= l && r <= qr) return sum[p];
    pushdown(p, l, r);                 // 同样要先还账
    int mid = (l + r) >> 1;
    return query(p << 1, l, mid, ql, qr)
         + query(p << 1 | 1, mid + 1, r, ql, qr);
}

口诀记一下：下放前必 pushdown，回溯时必 pushup。这两句忘了任何一句，答案就玄学出错。

洛谷 P3372（区间加区间和）是这道题的模板题。

常见坑

  1. 空间开小：2p 编号要开 4n，不是 2n。RE 的一大来源。
  2. 取模忘乘：区间长度 (r - l + 1) 别忘了乘，特别是带取模的时候。
  3. query 边界：ql <= l && r <= qr 和 qr < l || r < ql 这两行写反或写漏，样例可能碰巧过，大数据直接挂。
  4. 懒标记种类：加法标记可以直接累加；如果同时有”区间赋值”和”区间加”，要规定好先后顺序（一般是赋值覆盖加法）。
  5. 长整型：区间和 int 很容易溢出，无脑 long long。

练习题单

题目 考点
洛谷 P3374 单点修改 + 区间和
洛谷 P3372 区间加 + 区间和（懒标记入门）
洛谷 P1531 单点修改 + 区间最大值
洛谷 P1198 单点插入 + 区间最大值
洛谷 P1531 动态开点 / 离散化前热身

学会上面的模板之后，下一步可以看：权值线段树（配合离散化）、zkw 线段树（非递归写法，常数小）、线段树合并与分裂、李超线段树。那些都是这篇骨架上的变形——骨架熟了，后面的都不难。