线段树（Segment Tree）

数据结构与算法专题 · 区间查询与更新的高效数据结构

专题：数据结构与算法系统学习

关键词：数据结构, 算法, 线段树, Segment Tree, 区间查询, 区间更新, Lazy Propagation, 延迟标记

一、概述

线段树（Segment Tree）是一种二叉搜索树，它将一个区间划分成若干个单元区间，每个单元区间对应线段树中的一个叶子节点。线段树是算法竞赛和工程开发中解决区间问题的利器，能够在 O(log n) 的时间复杂度内完成区间查询（如求和、最大值、最小值）和区间更新操作。

线段树的核心思想是分治——将大区间递归分解为小区间，每个节点维护其对应子区间的聚合信息。通过这种树形结构，我们可以在不遍历整个数组的前提下快速获取任意区间的统计信息。

线段树支持的主要操作包括：区间查询（Range Query）、单点更新（Point Update）、区间更新（Range Update），其中区间更新配合 Lazy Propagation（延迟标记）技术同样能达到 O(log n) 的复杂度。

核心特性：线段树用空间换时间，以 O(n) 的预处理时间和 O(n) 的存储空间，换取 O(log n) 的查询与更新性能，非常适合处理静态数据上的动态区间操作。

二、基本概念与数据结构定义

2.1 区间分解原理

给定一个长度为 n 的数组 arr，线段树将区间 [0, n-1] 作为根节点，然后递归地将每个节点区间二等分，直到区间长度为 1（即单元素区间，对应叶子节点）。每个节点负责维护其对应区间上的某种聚合值（和、最大值、最小值等）。

例如，对于数组 arr = [1, 3, 5, 7, 9, 11]，区间 [0, 5] 被分解为：

2.2 节点与数组存储

线段树通常使用数组来存储，而非显式的树节点对象。假设根节点存储在索引 1 处，那么对于节点 i：

2.3 4 倍空间原则

线段树的数组大小通常开为 4 * n。这是因为一棵满二叉树在最坏情况下需要约 4n 的空间来存储所有节点（原因在于线段树不是完全二叉树，最后一层可能有空位）。具体来说，一棵有 n 个叶子节点的线段树，其总节点数不超过 4n。

空间推导：线段树的高度为 ⌈log₂n⌉ + 1，满二叉树节点数为 2^(h+1) - 1 ≈ 4n。因此开 4n 的数组可以确保空间充足。

2.4 数据结构定义（Python）

class SegmentTree: def __init__(self, arr): self.n = len(arr) self.tree = [0] * (4 * self.n) # 4倍空间 self.lazy = [0] * (4 * self.n) # 延迟标记数组 self.build(1, 0, self.n - 1, arr) # 建树：递归构造 def build(self, node, l, r, arr): if l == r: # 叶子节点 self.tree[node] = arr[l] return mid = (l + r) // 2 self.build(node * 2, l, mid, arr) self.build(node * 2 + 1, mid + 1, r, arr) self.tree[node] = self.tree[node * 2] + self.tree[node * 2 + 1]

三、线段树的建树（递归构造与数组存储）

建树过程采用递归方式，自顶向下将区间二分，到达叶子节点时填入原始数组的值，然后回溯时将子节点的值合并到父节点。合并操作取决于线段树维护的信息类型：求和树用加法，最大值树用 max，最小值树用 min。

3.1 建树过程详解

以 arr = [1, 3, 5, 7, 9, 11] 为例，建树过程如下：

  1. 调用 build(1, 0, 5)：代表从根节点（编号1）开始构建区间 [0, 5]
  2. mid = 2，递归构建左子树 build(2, 0, 2) 和右子树 build(3, 3, 5)
  3. build(2, 0, 2)：mid = 1，再分 build(4, 0, 1) 和 build(5, 2, 2)
  4. build(4, 0, 1)：mid = 0，分 build(8, 0, 0) 和 build(9, 1, 1)
  5. build(8, 0, 0)：l == r，tree[8] = arr[0] = 1，返回
  6. build(9, 1, 1)：l == r，tree[9] = arr[1] = 3，返回
  7. 回溯：tree[4] = tree[8] + tree[9] = 1 + 3 = 4
  8. build(5, 2, 2) 返回 tree[5] = arr[2] = 5
  9. 回溯：tree[2] = tree[4] + tree[5] = 4 + 5 = 9
  10. 以此类推，最终 tree[1] = 36（即数组总和）

3.2 建树代码实现（求和线段树）

def build(self, node, l, r, arr): """ node: 当前节点在线段树数组中的索引 l, r : 当前节点负责的区间范围 [l, r] arr : 原始数组 """ if l == r: self.tree[node] = arr[l] return mid = (l + r) // 2 self.build(node * 2, l, mid, arr) self.build(node * 2 + 1, mid + 1, r, arr) # 回溯时合并子节点的值 self.tree[node] = self.tree[node * 2] + self.tree[node * 2 + 1] # 调用方式： # seg = SegmentTree(arr) # 构造完成后，tree[1] 存储整个数组的区间和

时间复杂度：建树过程需要遍历所有节点，每个节点计算一次合并操作，总共有 2n-1 个节点（对于 n 个叶子节点的满二叉树），因此建树的时间复杂度为 O(n)。

四、区间查询（Range Query）

区间查询是线段树最核心的操作之一。给定查询区间 [ql, qr]，我们需要在线段树中找出完全位于 [ql, qr] 内的所有节点，并将它们的值合并起来。这一过程同样采用递归实现。

4.1 查询算法流程

递归查询函数 query(node, l, r, ql, qr) 的流程如下：

  1. 完全包含：如果 [l, r] 完全位于 [ql, qr] 内，直接返回 tree[node] 的值
  2. 完全无关：如果 [l, r] 与 [ql, qr] 没有交集，返回单位元（求和返回0，求最大值返回 -inf）
  3. 部分重叠：否则递归查询左右子节点，合并结果后返回

4.2 查询代码实现

def query(self, node, l, r, ql, qr): """ 查询区间 [ql, qr] 的和 node: 当前节点索引 l, r : 当前节点覆盖的区间范围 ql, qr: 查询区间范围 """ if ql <= l and r <= qr: return self.tree[node] # 完全包含，直接返回 if r < ql or l > qr: return 0 # 无交集，返回单位元（求和为0） mid = (l + r) // 2 left_res = self.query(node * 2, l, mid, ql, qr) right_res = self.query(node * 2 + 1, mid + 1, r, ql, qr) return left_res + right_res # 调用方式： # seg.query(1, 0, n-1, 2, 4) # 查询区间 [2, 4] 的和

4.3 查询过程图解分析

假设 arr = [1, 3, 5, 7, 9, 11]，查询区间 [2, 4] 的和：

时间复杂度分析：区间查询每次递归将查询区间最多分割到 O(log n) 个节点上，每个节点只访问一次，因此单次查询的时间复杂度为 O(log n)。最坏情况下（查询整个数组）也只需访问 O(log n) 个节点。

五、区间更新（Range Update）

区间更新分为两种情况：单点更新和区间更新。单点更新只需修改一个叶子节点并更新其所有祖先节点即可，实现简单。区间更新则需要将一段连续区间内的所有元素统一修改（如全部加上某个值），如果逐点更新，时间复杂度将退化为 O(n log n)。为此我们需要引入Lazy Propagation（延迟标记）技术。

5.1 单点更新

单点更新只需要找到对应的叶子节点，修改其值，然后回溯更新路径上的所有父节点。

def point_update(self, node, l, r, idx, val): """ 将 arr[idx] 更新为 val """ if l == r: # 找到叶子节点 self.tree[node] = val return mid = (l + r) // 2 if idx <= mid: self.point_update(node * 2, l, mid, idx, val) else: self.point_update(node * 2 + 1, mid + 1, r, idx, val) self.tree[node] = self.tree[node * 2] + self.tree[node * 2 + 1] # 时间复杂度：O(log n)

六、Lazy Propagation（延迟标记）

当我们需要对区间 [2, 5] 内的所有元素都加上 3 时，如果使用单点更新逐个修改，需要更新 n 个点，每个点 O(log n)，总复杂度 O(n log n)。Lazy Propagation 的核心思想是：推迟更新——当更新区间完全覆盖当前节点区间时，只修改当前节点的值并打上延迟标记，不再递归向下更新子节点。等到将来需要查询或更新子节点时，再将标记下推（push down），确保子节点的数据一致性。

6.1 延迟标记的工作原理

  1. 打标记：更新操作递归到某节点时，如果更新区间完全覆盖该节点区间，则修改该节点 tree[node] 的值，同时在 lazy[node] 中记录待下推的更新信息
  2. 下推标记（push）：当需要访问某节点的子节点时（如后续的查询或更新），先将当前节点的 lazy 标记下推到子节点中，并更新子节点的值，然后清除当前节点的 lazy 标记

6.2 完整实现代码

class SegmentTree: def __init__(self, arr): self.n = len(arr) self.tree = [0] * (4 * self.n) self.lazy = [0] * (4 * self.n) self._build(1, 0, self.n - 1, arr) def _build(self, node, l, r, arr): if l == r: self.tree[node] = arr[l] return mid = (l + r) // 2 self._build(node * 2, l, mid, arr) self._build(node * 2 + 1, mid + 1, r, arr) self.tree[node] = self.tree[node * 2] + self.tree[node * 2 + 1] def _push(self, node, l, r): """下推延迟标记""" if self.lazy[node] != 0 and l != r: mid = (l + r) // 2 # 下推到左孩子 self.tree[node * 2] += self.lazy[node] * (mid - l + 1) self.lazy[node * 2] += self.lazy[node] # 下推到右孩子 self.tree[node * 2 + 1] += self.lazy[node] * (r - mid) self.lazy[node * 2 + 1] += self.lazy[node] # 清除当前节点的标记 self.lazy[node] = 0 def range_update(self, node, l, r, ul, ur, val): """ 将区间 [ul, ur] 内的所有元素加上 val """ if ul <= l and r <= ur: # 完全覆盖，修改当前节点并打标记 self.tree[node] += val * (r - l + 1) self.lazy[node] += val return self._push(node, l, r) # 下推已有标记 mid = (l + r) // 2 if ul <= mid: self.range_update(node * 2, l, mid, ul, ur, val) if ur > mid: self.range_update(node * 2 + 1, mid + 1, r, ul, ur, val) self.tree[node] = self.tree[node * 2] + self.tree[node * 2 + 1] def range_query(self, node, l, r, ql, qr): """带延迟标记的区间查询""" if ql <= l and r <= qr: return self.tree[node] self._push(node, l, r) # 查询前先下推标记 mid = (l + r) // 2 res = 0 if ql <= mid: res += self.range_query(node * 2, l, mid, ql, qr) if qr > mid: res += self.range_query(node * 2 + 1, mid + 1, r, ql, qr) return res # 使用示例： # seg = SegmentTree([1, 3, 5, 7, 9, 11]) # seg.range_update(1, 0, 5, 2, 4, 3) # 下标2~4全部+3 # print(seg.range_query(1, 0, 5, 1, 3)) # 查询区间 [1,3]

6.3 延迟标记的正确性保证

Lazy Propagation 的精髓在于标记只在需要时下推。当我们进行区间更新时，遇到完全覆盖的节点就打标记停止递归；当我们进行区间查询遇到完全覆盖的节点就直接返回当前值（标记保留）；只有当我们递归到子节点时，才需要下推标记以保证子节点值的正确性。这一机制保证了：

注意事项：延迟标记的类型取决于更新操作。对于区间加（add操作），标记是累加的；对于区间赋值（set操作），标记是覆盖的，下推逻辑需要相应调整。混合操作（既有 add 又有 set）需要传递多个标记并进行优先级排序。

七、线段树的应用场景

线段树的应用范围极其广泛，几乎任何需要高效区间操作的问题都可以考虑使用线段树。以下是几种典型的应用场景。

7.1 区间最值查询（RMQ）

Range Minimum/Maximum Query 是线段树最经典的应用之一。构建最大值线段树，每个节点存储区间最大值，查询和更新都只需 O(log n)。

# 最大值线段树的合并逻辑 def build_max(self, node, l, r, arr): if l == r: self.tree[node] = arr[l] return mid = (l + r) // 2 self.build_max(node * 2, l, mid, arr) self.build_max(node * 2 + 1, mid + 1, r, arr) self.tree[node] = max(self.tree[node * 2], self.tree[node * 2 + 1]) # 最大值查询，不重叠时返回 -inf def query_max(self, node, l, r, ql, qr): if ql <= l and r <= qr: return self.tree[node] if r < ql or l > qr: return -10**9 # 负无穷 mid = (l + r) // 2 return max(self.query_max(node * 2, l, mid, ql, qr), self.query_max(node * 2 + 1, mid + 1, r, ql, qr))

7.2 区间和与区间乘积

区间和线段树是最基础的形式（前面的示例均以区间和为例）。区间乘积线段树原理相同，只需将合并操作改为乘法即可，但需注意数值溢出问题（常需要取模）。

7.3 区间最大子段和

这是一个经典的线段树进阶应用。每个节点需要维护四个信息：区间和 sum、区间最大前缀和 pre、区间最大后缀和 suf、区间最大子段和 max_sub。

class NodeInfo: def __init__(self, sum_val=0, pre=0, suf=0, max_sub=0): self.sum = sum_val # 区间总和 self.pre = pre # 区间最大前缀和 self.suf = suf # 区间最大后缀和 self.max_sub = max_sub # 区间最大子段和 def merge(self, left, right): """合并两个子区间的信息""" res = NodeInfo() res.sum = left.sum + right.sum res.pre = max(left.pre, left.sum + right.pre) res.suf = max(right.suf, right.sum + left.suf) res.max_sub = max(left.max_sub, right.max_sub, left.suf + right.pre) return res # 利用线段树可以在 O(log n) 内查询任意区间的最大子段和

7.4 权值线段树与离散化

权值线段树是一种特殊的线段树，它的叶子节点代表值域而非数组下标。每个节点统计落在该值域区间内的元素个数。权值线段树可用于：

7.5 扫描线算法

线段树是扫描线算法（Sweep Line）的核心数据结构，用于计算矩形面积并、矩形周长并等几何问题。扫描线算法将矩形的上下边沿 x 坐标排序，用线段树维护 y 轴方向的覆盖长度，每处理一条边就更新覆盖长度并累加面积。

扫描线核心思想：将二维问题转化为一维区间问题。每个矩形用两条水平边表示（入边和出边），线段树维护当前被覆盖的 y 轴区间长度，乘以 x 方向的增量即为面积元。

7.6 可持久化线段树（主席树）

可持久化线段树（Persistent Segment Tree，又称主席树）是线段树的高阶变体。每次修改操作都创建一个新的版本，保留所有历史版本，从而支持历史版本查询和区间第 K 大等问题。其核心技巧是每次更新只创建 O(log n) 个新节点（被修改的路径），其余节点复用旧版本，空间复杂度 O(n log n)。

八、线段树 vs 树状数组（Fenwick Tree）

树状数组（Binary Indexed Tree, BIT 或 Fenwick Tree）是与线段树功能相似但实现更简洁的数据结构。二者各有优劣，理解它们的区别有助于在具体问题中选择合适的工具。

对比维度 线段树（Segment Tree） 树状数组（Fenwick Tree）
代码复杂度 较复杂，需要递归/建树/标记下推 非常简洁，核心只有几行
空间复杂度 O(4n) O(n)
单点更新+区间查询 O(log n) O(log n)
区间更新+区间查询 O(log n) 支持（Lazy） 需差分技巧，较复杂
区间最值 O(log n) 直接支持 不支持（或需复杂扩展）
可持久化 支持（主席树） 不支持
非交换操作（如矩阵乘法） 支持 不支持
适用场景 复杂区间操作、多种信息维护 简单前缀和、逆序对

选型建议：如果问题只需要单点更新和前缀和查询，树状数组是更轻量的选择。如果涉及区间更新、区间最值、非交换运算或需要维护多种聚合信息，则线段树是更通用的方案。在算法竞赛中，线段树往往作为"万能工具"使用，因其可扩展性远超树状数组。

8.1 树状数组代码示例（对比参考）

class FenwickTree: def __init__(self, n): self.n = n self.bit = [0] * (n + 1) def add(self, idx, delta): """单点增加""" i = idx + 1 # 树状数组 1-indexed while i <= self.n: self.bit[i] += delta i += i & -i # lowbit def sum(self, idx): """前缀和 [0, idx]""" i = idx + 1 res = 0 while i > 0: res += self.bit[i] i -= i & -i return res def range_sum(self, l, r): """区间和 [l, r]""" return self.sum(r) - self.sum(l - 1) # 树状数组核心：lowbit(x) = x & -x # 空间 O(n)，代码极简，但功能受限

九、总结与进阶学习路径

线段树核心要点回顾：

  • 数据结构本质：二叉树 + 分治，每个节点维护一个区间的聚合信息
  • 存储方式：数组存储，根节点索引1，左子 2i, 右子 2i+1，空间 4n
  • 建树：递归二分，回溯合并，时间复杂度 O(n)
  • 区间查询：递归搜索完全覆盖的节点，合并结果，O(log n)
  • 区间更新：Lazy Propagation 延迟标记，完全覆盖时打标记不递归，O(log n)
  • 标记下推：在访问子节点前下推当前节点的延迟标记，保证数据一致性

进阶学习路径

掌握基础线段树后，可以按以下路径深入：

  1. 基础巩固：熟练实现带 Lazy 的线段树，完成「线段树模板题」（洛谷 P3372、P3373）
  2. 权值线段树：理解值域建树，实现求第 K 大、逆序对统计
  3. 动态开点线段树：不预先开满 4n 空间，在需要时动态创建节点，适合值域大但数据稀疏的场景
  4. 线段树合并：将两棵权值线段树合并，用于树上问题（如 dsu on tree）
  5. 可持久化线段树：保留历史版本，经典应用如「静态区间第 K 小」（洛谷 P3834）
  6. 线段树优化建图：利用线段树的区间分解特性优化建图，将 O(n²) 的边数降到 O(n log n)
  7. 线段树分治：离线处理需要撤销操作的动态问题，按时间轴建线段树

算法竞赛提示：线段树是 NOI/ACM 的必考知识点。建议从模板题入手，熟练默写四种核心操作（建树、查询、更新、下推），再逐步攻克进阶应用。理解递归过程和区间分解思想是掌握线段树的关键。

常见误区与调试技巧