你不得不学的线段树 (segment tree) 基础 🌳

你不得不学的线段树基础 🌳

最近刷力扣时遇到了很多和线段树有关的题目，所以这篇博客是用来讲解 线段树 的。

线段树是算法竞赛和面试中常用的数据结构，专门用来高效处理区间信息。它能在 $O(\log N)$ 的时间复杂度内完成区间查询（求和、求最值等）和区间修改操作，将原本 $O(N)$ 的操作大幅优化。

为什么需要线段树？

想象一下，你有一个长度为 $N$ 的数组，你需要频繁地进行以下两种操作：

  1. 查询操作：求出数组中 $[l, r]$ 区间内所有元素的和（或最大值、最小值等）
  2. 修改操作：将数组中 $[l, r]$ 区间内的每个元素都加上某个值

如果直接遍历数组：

  • 查询操作需要 $O(N)$ 时间
  • 修改操作也需要 $O(N)$ 时间

线段树的基本结构

线段树的核心思想是分治：将一个区间不断地二分，直到区间长度为1（叶子节点），每个节点存储其对应区间的某种聚合信息（如和、最大值等）。

存储方式

线段树通常用数组以完全二叉树的形式存储：

  • 根节点下标为 1
  • 对于节点 p，其左子节点为 p*2，右子节点为 p*2+1
  • 叶子节点对应原始数组的单个元素

让我们通过一个具体例子来理解。假设有数组 $a = [10, 11, 12, 13, 14]$：

1
2
3
4
5
6
7
8
9
10
11
12
# 原始数组
a = [10, 11, 12, 13, 14]

# 对应的线段树（存储区间和）
树结构如下：
           [1,5]:60
          /        \
     [1,3]:33      [4,5]:27
     /    \        /    \
[1,2]:21  [3,3]:12 [4,4]:13 [5,5]:14
  /   \
[1,1]:10 [2,2]:11

如何计算节点编号？

  • 根节点（管理区间[1,5]）编号为1
  • 其左子节点（管理区间[1,3]）编号为2（1×2）
  • 其右子节点（管理区间[4,5]）编号为3（1×2+1）

每个节点存储它管理区间的聚合信息（这里是区间和）。

建树过程

建树采用递归二分的方式：

  1. 如果当前区间长度为1（叶子节点），直接存储该元素的值
  2. 否则，将区间分为两半：
    • 左半部分递归建树
    • 右半部分递归建树
  3. 回溯时，用左右子节点的信息计算当前节点的值
1
2
3
4
5
6
7
8
def build(p, s, t):
    if s == t:
        d[p] = arr[s]
        return
    m = s + t >> 1
    build(2 * p, s, m)
    build(2 * p + 1, m + 1, t)
    d[p] = d[2 * p] + d[2 * p + 1]

空间复杂度分析

线段树需要 $4N$ 的空间来存储：

  • 深度为 $\lceil \log N \rceil$
  • 总节点数不超过 $2 \times 2^{\lceil \log N \rceil} - 1 \approx 4N$

为什么是4N？

考虑最坏情况：当 $N = 2^x + 1$ 时（如N=9），需要大约 $4N - 5$ 个节点。为保险起见，我们直接分配 $4N$ 的空间。

区间查询

现在我们要查询区间 $[l, r]$ 的和。基本思想是：

  1. 如果查询区间完全覆盖当前节点区间，直接返回该节点值
  2. 否则，将查询区间拆分，递归查询左右子树，合并结果

可合并的查询结果

可合并的区间查询指的是查询结果可以通过满足结合律的操作，由两个相邻子区间的结果快速合并得到整个区间的结果，如区间和、区间最值。

1
2
3
4
5
6
7
8
9
10
def query(p, s, t, l, r):
    if l <= s and t <= r:
        return d[p]
    m = s + t >> 1
    ret = 0
    if l < m:
        ret += query(2 * p, s, m, l, r)
    if r >= m:
        ret += query(2 * p + 1, m + 1, t, l, r)
    return ret

查询时间复杂度：$O(\log N)$，因为每次递归都将区间长度减半。

区间修改与懒标记

如果每次区间修改都更新所有相关节点，时间复杂度会退化为 $O(N)$。例如，将区间 $[1, 1000]$ 的每个元素都加1，传统方法需要修改1000个叶子节点！

为此引入懒标记（Lazy Propagation）技术，延迟对子节点的更新。

懒标记原理

想象一下，你是一个经理，有一个任务要分配给整个部门。你有两个选择：

  1. 亲自告诉每个员工（效率低下）
  2. 告诉部门主管，让他以后找时间通知员工（高效）

懒标记就采用了第二种思路：

  • 修改时：只在完全覆盖的节点上更新值并打上标记
  • 查询时：如果遇到有标记的节点，先将标记下传给子节点
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
36
# 区间修改
def update(p, s, t, l, r, v):
    if l <= s and t <= r:
        d[p] += v * (l - r + 1)
        lazy[p] += v # 懒标记
        return
    m = s + t >> 1
    if lazy[p] and s != t: # 当懒标记非空时下传
        d[2 * p] += lazy[p] * (m - s + 1)
        d[2 * p + 1] += lazy[p] * (t - m)
        lazy[2 * p] += lazy[p]
        lazy[2 * p + 1] += lazy[p]
        lazy[p] = 0
    if l <= m:
        update(2 * p, s, m, l, r, v)
    if r > m:
        update(2 * p + 1, m + 1, t, l, r, v)
    d[p] = d[2 * p] + d[2 * p + 1]

# 区间查询
def query(p, s, t, l, r):
    if l <= s and t < = r:
        return d[p]
    m = s + t >> 1
    if lazy[p]: # 当懒标记非空时下传
        d[2 * p] += lazy[p] * (m - s + 1)
        d[2 * p + 1] = lazy[p] * (t - m)
        lazy[2 * p] += lazy[p]
        lazy[2 * p + 1] += lazy[p]
        lazy[p] = 0
    ret = 0
    if l <= m:
        ret += query(2 * p, s, m, l, r)
    if r > m:
        ret += query(2 * p + 1, m + 1, t, l, r)
    return ret

懒标记的时空复杂度

  • 时间复杂度：每次更新和查询都是 $O(\log N)$
  • 空间复杂度：需要额外的 $4N$ 空间存储懒标记

动态开点线段树

传统线段树需要预先分配 $4N$ 空间，对于区间范围很大（如 $[1, 10^9]$）但操作较少的场景会造成空间浪费。动态开点线段树在需要时才创建节点，节省空间。

核心思想

  • 不建立完全二叉树结构
  • 只有访问到的节点才会被创建
  • 用字典或对象记录左右子节点引用
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
d = [0] * (2 * n)
ls = [0] * (2 * n) # 左子节点索引
rs = [0] * (2 * n) # 右子节点索引
cnt = 0 # 记录节点数量

# 单点更新
def update(p, s, t, x, v): # x 是要修改的节点
    if p == 0:
        cnt += 1
        p = cnt # 开新节点
    if s == t: # 找到目标节点
        d[p] += v
        return
    m = s + t >> 1
    if x <= m:
        update(ls[p], s, m, x, v)
    else:
        update(rs[p], m + 1, t, x, v)
    d[p] = d[ls[p]] + d[rs[p]]

# 区间查询
def query(p, s, t, l, r):
    if p == 0:
        return 0
    if l <= s and t <= r:
        return d[p]
    m = s + t >> 1
    ret = 0
    if l <= m:
        ret += query(ls[p], s, m, l, r)
    if r > m:
        ret += query(rs[p], m + 1, t, l, r)

动态开点 vs 静态线段树

特性 静态线段树 动态开点线段树
空间复杂度 $O(4N)$ $O(K \log R)$，K为操作次数，R为值域
适用场景 区间范围已知且适中 值域很大但操作较少
实现复杂度 简单 较复杂
内存分配 一次性分配 按需分配

总结与反思

线段树是解决区间问题的强大工具，理解其核心思想后，可以扩展到各种变体：

常见线段树变体

  1. 最大值/最小值线段树：节点存储区间最大/最小值
  2. 区间赋值线段树：支持将区间设为固定值
  3. 区间乘加线段树：支持乘法和加法混合操作
  4. 可持久化线段树（主席树）：保存历史版本
  5. 权值线段树：维护值域统计信息

线段树优化技巧

  1. 标记永久化：不下传懒标记，在查询时累加路径上的标记
  2. zkw线段树：非递归实现，常数更小
  3. 线段树合并：合并两棵线段树的信息
  4. 线段树分裂：将一棵线段树按值域分裂成两棵

与线段树有关的题单

💻 技术干货 > 数据结构与算法
#数据结构与算法 #线段树 #树结构
你不得不学的线段树 (segment tree) 基础 🌳
http://example.com/2025/12/06/segment-tree/
Author
LazyPool
Posted on
December 6, 2025
Licensed under