线段树

定义

线段树（Segment Tree）是一种二叉树形数据结构，用于高效地处理区间查询和区间修改问题。线段树将一个区间递归地划分为两个子区间，直到每个子区间只包含一个元素为止。¹

线段树支持的主要操作包括：

• 区间查询：在 $O(\log n)$ 时间复杂度内查询区间和、区间最大值、区间最小值等
• 区间修改：在 $O(\log n)$ 时间复杂度内对区间进行加法、赋值等操作

线段树的核心思想是：空间换时间。通过预处理，将区间信息存储在树节点中，使得查询和修改操作只需访问 $O(\log n)$ 个节点。

基本结构与建树

结构特点

线段树是一棵完全二叉树，每个节点代表一个区间：

• 根节点代表整个区间 $[1,n]$
• 每个节点的左子节点代表区间 $[l,mid]$，右子节点代表区间 $[mid+1,r]$
• 叶子节点代表单个元素 $[i,i]$

数组表示

线段树通常使用数组存储，节点编号遵循以下规则：

• 根节点编号为 $1$
• 节点 $p$ 的左子节点编号为 $p\times 2$，右子节点编号为 $p\times 2+1$

由于线段树的高度约为 $\lceil {\log }_{2}n\rceil$，因此数组大小通常设置为 $4n$ 即可安全存储所有节点。

建树过程

给定数组 $a[\mathrm{1...}n]$，建树过程如下：

void build(int s, int t, int p, vector<int>& a, vector<long long>& d) {
    if (s == t) {
        d[p] = a[s];
        return;
    }
    int m = s + ((t - s) >> 1);
    build(s, m, p * 2, a, d);
    build(m + 1, t, p * 2 + 1, a, d);
    d[p] = d[p * 2] + d[p * 2 + 1];
}

建树的时间复杂度为 $O(n)$，空间复杂度为 $O(n)$。

区间查询

区间查询是线段树最核心的操作之一。给定查询区间 $[l,r]$，我们从根节点出发，递归地向下查找：

1. 如果当前节点完全包含在查询区间内，直接返回该节点的值
2. 如果当前节点与查询区间无交集，返回默认值（如 $0$）
3. 否则，递归查询左右子节点并合并结果

查询区间和

long long query(int l, int r, int s, int t, int p, const vector<long long>& d) {
    if (l <= s && t <= r) return d[p];
    int m = s + ((t - s) >> 1);
    long long sum = 0;
    if (l <= m) sum += query(l, r, s, m, p * 2, d);
    if (r > m) sum += query(l, r, m + 1, t, p * 2 + 1, d);
    return sum;
}

查询区间最大值 / 最小值

对于区间最大值查询，只需将合并操作从求和改为 max；对于区间最小值，改为 min。

时间复杂度分析

单次区间查询的时间复杂度为 $O(\log n)$，因为每次递归都会将区间减半，最多递归 $O(\log n)$ 层。

区间修改与懒惰标记

朴素区间修改的问题

如果直接对区间 $[l,r]$ 的每个元素进行修改，时间复杂度为 $O(n)$，无法发挥线段树的优势。

懒惰传播的思想

懒惰传播（Lazy Propagation）的核心思想是：当需要修改一个区间时，不立即向下更新所有子节点，而是将修改记录”标记”在当前节点上，等到下次查询时再将标记下推。

具体来说：

• 每个节点维护一个「懒惰标记」$b[p]$，表示该节点需要向下传递的修改量
• 当区间完全被覆盖时，更新当前节点的值，并记录懒惰标记
• 当需要访问子节点时，将懒惰标记下推，更新子节点的值和子节点的懒惰标记

区间修改实现

void update(int l, int r, long long c, int s, int t, int p, 
            vector<long long>& d, vector<long long>& b) {
    if (l <= s && t <= r) {
        d[p] += (t - s + 1) * c;
        b[p] += c;
        return;
    }
    int m = s + ((t - s) >> 1);
    if (b[p]) {
        d[p * 2] += b[p] * (m - s + 1);
        d[p * 2 + 1] += b[p] * (t - m);
        b[p * 2] += b[p];
        b[p * 2 + 1] += b[p];
        b[p] = 0;
    }
    if (l <= m) update(l, r, c, s, m, p * 2, d, b);
    if (r > m) update(l, r, c, m + 1, t, p * 2 + 1, d, b);
    d[p] = d[p * 2] + d[p * 2 + 1];
}

懒惰标记的下推

当节点 $p$ 有未下推的懒惰标记 $b[p]$ 时：

$$\begin{array}{rl}d[p\times 2]& =d[p\times 2]+b[p]\times (mid-s+1)\\ d[p\times 2+1]& =d[p\times 2+1]+b[p]\times (t-mid)\\ b[p\times 2]& =b[p\times 2]+b[p]\\ b[p\times 2+1]& =b[p\times 2+1]+b[p]\\ b[p]& =0\end{array}$$

常见题型

区间加法与区间求和

这是最基本的线段树应用，支持两种操作：

1. add(l, r, v)：将区间 $[l,r]$ 内所有元素加上 $v$
2. query(l, r)：查询区间 $[l,r]$ 的和

区间赋值与区间求和

某些题目要求区间赋值为某个值，而非加上某个值。此时懒惰标记的处理方式略有不同：赋值操作会覆盖之前的操作，因此需要将「加法标记」改为「赋值标记」。

区间乘法与区间求和

当需要支持区间乘法时，懒惰标记需要维护两个值：加法标记和乘法标记。标记下推时：

$$\begin{array}{rl}d[p\times 2]& =d[p\times 2]\times mul+add\times len\\ mul[p\times 2]& =mul[p\times 2]\times mul\\ add[p\times 2]& =add[p\times 2]\times mul+add\end{array}$$

区间最大 / 最小值查询

只需将合并操作从求和改为 max 或 min 即可。注意：区间最值查询通常不需要懒惰标记，因为查询操作本身不会修改数据。

应用场景

线段树广泛应用于以下场景：

应用场景	说明
区间求和	统计数组某段区间的元素之和
区间最值	快速查询区间最大（小）值
区间修改	对区间进行批量加法、赋值等操作
离线查询	结合离散化处理大规模区间问题
其他	可扩展为树状数组、二维线段树等变体

线段树与 堆、并查集 等数据结构一样，是竞赛和工程中常用的基础工具。

参考资料

Footnotes

1. 本段参考线段树 - OI Wiki ↩