跳转到内容
← 返回算法
数据结构计算机科学 · 算法 · 数据结构约 22 分钟阅读

线段树

Segment Trees

考虑一个百万元素的数组，要回答几十万次这样的问询："第 30000 到 80000 个元素之和是多少？"——而且元素的值还会不断被修改。 朴素地每次从头加一遍，单次查询要扫 $n$ 个元素；一百万元素、十万次查询就是 $10^{11}$ 次加法，普通 CPU 要跑上分钟。线段树把单次查询和单次修改都压到 $\log2 …

线段树区间查询数据结构竞技编程懒惰传播

考虑一个百万元素的数组，要回答几十万次这样的问询："第 30000 到 80000 个元素之和是多少？"——而且元素的值还会不断被修改。

朴素地每次从头加一遍，单次查询要扫 $n$ 个元素；一百万元素、十万次查询就是 101110^{11} 次加法，普通 CPU 要跑上分钟。线段树把单次查询和单次修改都压到 log⁡2106≈20\log_2 10^6 \approx 20 步，同样的工作量降到约 2×1062\times10^6 次操作——快了五个数量级。

这个数据结构由乔恩·本特利（Jon Bentley）在 1977 年提出，最初的用途不是数组求和，而是计算几何里的一个问题：给定平面上一堆线段，问一个点落在其中多少条线段内（stabbing query）。今天它在竞技编程、数据库、游戏引擎里随处可见。

问题背景

区间查询问题（Range Query Problem）：给定数组 $a[0..n-1]$，支持： - 查询：计算 $a[l..r]$ 的某个聚合值（和、最大值、最小值、GCD 等） - 更新：修改 $a[i]$ 的值

方案查询复杂度更新复杂度
朴素扫描$O(n)$$O(1)$
前缀和$O(1)$$O(n)$
线段树O(log⁡n)O(\log n)O(log⁡n)O(\log n)

这张表最该注意的是前两行的对称性：朴素扫描把全部代价压给查询，前缀和把全部代价压给更新，两者都在某一侧退化成 $O(n)$。线段树是把代价摊到两侧的经典方案——两个操作都不最优，但都不会烂。

结构：二叉树上的区间分解

线段树的每个节点存储一段区间 $[l, r]$ 的聚合值，根节点存储 $[0, n-1]$ 的聚合。每个内部节点 $[l, r]$（$l < r$）的两个子节点分别对应 $[l, m]$ 和 $[m+1, r]$（m=⌊(l+r)/2⌋m = \lfloor(l+r)/2\rfloor），叶节点对应单个元素。这套划分规则是固定的——它只取决于 $n$，不取决于你查什么。所以树里那些区间被称为标准区间（canonical intervals）：全部可能的 O(n2)O(n^2) 个区间中，只有 $2n-1$ 个能在树上找到一个节点直接代表它，其余的都必须拼出来。

以区间和为例，取数组 $a = [1,2,3,4,5,6,7,8]$，$n = 8$ 的线段树是：

                [0,7]: 36
               /           \
         [0,3]: 10        [4,7]: 26
        /       \         /       \
    [0,1]:3  [2,3]:7  [4,5]:11  [6,7]:15
    /   \    /   \    /   \     /   \
  [0]:1 [1]:2 [2]:3 [3]:4 [4]:5 [5]:6 [6]:7 [7]:8
```

树的高度为 ⌈log⁡2n⌉\lceil \log_2 n \rceil，节点总数恰好 $2n - 1$（$n$ 个叶子加 $n-1$ 个内部节点）。但存这棵树的数组通常要开 $4n$——为什么多出一倍，下文有一节专门用一个 $n = 11$ 的例子说明。

走一遍：8 元素数组上的一次区间查询

抽象的"分解为 O(log⁡n)O(\log n) 个节点"听起来像魔法，走一遍就没有神秘感了。在上面这棵树上查 sum(a[2..6])\text{sum}(a[2..6])，答案应该是 $3+4+5+6+7 = 25$。

查询从根开始递归，每个节点只有三种命运：完全被查询区间覆盖（直接交出自己的值，不再往下走）、与查询区间不相交（返回单位元 0）、部分重叠（把问题分给两个孩子）。

步访问节点与 $[2,6]$ 的关系动作返回
1$[0,7]$部分重叠递归左右孩子（$m=3$）待定
2$[0,3]$部分重叠递归（$m=1$）待定
3$[0,1]$不相交剪掉，返回单位元0
4$[2,3]$完全覆盖直接交值，停止下降7
5$[0,3]$—合并 $0+7$7
6$[4,7]$部分重叠递归（$m=5$）待定
7$[4,5]$完全覆盖直接交值，停止11
8$[6,7]$部分重叠递归（$m=6$）待定
9$[6,6]$完全覆盖直接交值7
10$[7,7]$不相交剪掉0
11$[6,7]$—合并 $7+0$7
12$[4,7]$—合并 $11+7$18
13$[0,7]$—合并 $7+18$25

这张表最该注意的是第 4、7、9 行：整个查询的答案完全由三个"完全覆盖"节点贡献，$7 + 11 + 7 = 25$。$[2,6]$ 这个长度 5 的区间被恰好拆成了 [2,3]∪[4,5]∪[6,6][2,3] \cup [4,5] \cup [6,6] 三块，一块都不多。剩下的十步全是找路和剪枝的开销。

这就是复杂度的来源。两条界要分清：

  • 有效节点（拼出答案的那些）每层最多 2 个——因为查询区间的左端点和右端点各只能"切断"一条从根往下的路径，其他节点要么整块在内、要么整块在外。所以标准区间不超过 2⌈log⁡2n⌉2\lceil\log_2 n\rceil 个。
  • 访问节点每层最多 4 个——上面那 2 个有效节点的兄弟也会被摸一下（然后被剪掉）。本例逐层数一下：第 0 层 1 个、第 1 层 2 个（$[0,3]$、$[4,7]$）、第 2 层 4 个（$[0,1]$、$[2,3]$、$[4,5]$、$[6,7]$）、第 3 层 2 个（$[6,6]$、$[7,7]$），共 9 个不同节点，每层都没超过 4。所以总访问量不超过 4log⁡2n4\log_2 n。

换成 n=106n = 10^6：拼出答案的节点约 40 个，访问约 80 个。对比朴素扫描的一百万次加法——这就是那五个数量级。

核心操作

构建（Build） 自底向上，每个节点的值由两个子节点合并而来，一共 $2n-1$ 次合并，时间 $O(n)$。点更新（Point Update） 修改叶节点 $[i, i]$，然后沿这条唯一的路径向上重算每个祖先，时间 O(log⁡n)O(\log n)——注意这里不需要任何搜索，叶子位置直接算得出，改动只沿一条链传播。

区间查询（Range Query） 是唯一有分支逻辑的操作：把 $[l, r]$ 分解为 O(log⁡n)O(\log n) 个不相交的标准区间，合并它们的答案。

query(node, l, r):
  若 node 的区间完全在 [l, r] 内：返回 node.value
  若 node 的区间与 [l, r] 不相交：返回单位元
  m = 中点
  return merge(query(左子, l, r), query(右子, l, r))
```

三个分支——完全覆盖、不相交、部分重叠——就是全部逻辑。上一节的走查已经把这三种情况各撞过好几次。

懒惰传播：区间修改的利器

若需要支持区间修改（如将 $a[l..r]$ 全部加上 δ\delta），朴素方案需要更新所有叶节点，时间 $O(n)$。懒惰传播（Lazy Propagation） 的做法是给节点加一个"懒惰标记"，含义是"我的子树里所有元素都还欠加 δ\delta，但我没往下告诉它们"。只在查询或更新必须进入某个节点的孩子时，才把标记向下传递一层（Push Down），于是区间修改和区间查询都保持在 O(log⁡n)O(\log n)。这是线段树最精妙的设计之一：延迟执行不必要的操作，在真正需要时才执行。

手算一次区间加法：标记下推前后

还是那棵 a=[1,…,8]a = [1,\dots,8] 的树。执行 add(1, 6, +10)——把 $a[1..6]$ 每个元素加 10。总和应从 36 变成 36+6×10=9636 + 6\times10 = 96。

关键的一步在第 4 行和第 6 行：一个节点被查询区间完全覆盖时，我们不下降，而是就地把自己的聚合值加上 δ×\delta \times 区间长度，再挂一个标记留给孩子。

步节点关系动作值（旧 → 新）标记
1$[0,7]$部分递归36 → 96（回溯时算）0
2$[0,3]$部分递归10 → 400
3$[0,1]$部分递归3 → 130
4$[1,1]$覆盖就地加 10×110\times12 → 12叶子，无需标记
5$[2,3]$覆盖就地加 10×210\times2，停止下降7 → 27lazy = 10
6$[4,5]$覆盖就地加 10×210\times2，停止下降11 → 31lazy = 10
7$[6,6]$覆盖就地加 10×110\times17 → 17叶子
8$[6,7]$部分回溯合并 $17+8$15 → 250
9$[4,7]$—合并 $31+25$26 → 560
10$[0,7]$—合并 $40+56$36 → 960

$36 + 60 = 96$，对得上。注意此刻树里有两个说谎的地方：$[2,3]$ 的值 27 是对的，但它的孩子 $[2,2]=3$、$[3,3]=4$ 还是旧值；$[4,5]$ 同理。这就是"懒"的代价——正确性被推迟到有人真正需要往下看的那一刻。

现在查 sum(a[3..4])\text{sum}(a[3..4])，正确答案是 $(4+10)+(5+10)=29$。这次递归会撞上那两个说谎的节点：

步节点情况下推动作校验
1$[2,3]$部分重叠，且 lazy = 10必须先下推：$[2,2]$ 由 3 → 13，$[3,3]$ 由 4 → 14，lazy 清零$13+14=27$ = 父节点的值 ✓
2$[3,3]$覆盖返回 14
3$[4,5]$部分重叠，且 lazy = 10下推：$[4,4]$ 由 5 → 15，$[5,5]$ 由 6 → 16，lazy 清零$15+16=31$ = 父节点的值 ✓
4$[4,4]$覆盖返回 15
合计 $14+15$29 ✓

那两列"校验"是自己写线段树时最有用的调试不变量：下推之后，两个孩子的值之和必须等于父节点的值。这条等式一旦不成立，要么是下推公式漏乘了区间长度，要么是标记被重复应用了——这两个 bug 占了懒惰传播实现错误的绝大多数。

顺带一个容易忽略的设计约束：懒惰标记必须可复合。两次区间加法可以合并成一个标记（δ1+δ2\delta_1 + \delta_2），所以区间加好写；但"区间赋值"和"区间加"混用时，标记就变成了一个二元组，且两种操作不可交换（先赋值后加 ≠ 先加后赋值），必须显式定义复合顺序。哪些操作能上线段树，本质上取决于它的标记能不能构成一个可结合的复合运算。

为什么数组要开 4n

树只有 $2n-1$ 个节点，为什么教科书清一色写 int tree[4*n]？因为绝大多数实现用堆式下标——节点 $i$ 的孩子是 $2i$ 和 $2i+1$。这种编号不要求树是满的，一旦树的形状不规整，下标就会跳空。

拿 $n = 11$（下标 $0..10$）实际编一遍，只列最深的那几条链：

节点区间堆式下标由谁分裂而来
$[0,10]$1根
$[0,5]$ / $[6,10]$2 / 3$m = 5$
$[0,2]$ / $[3,5]$4 / 5$m = 2$
$[0,1]$8$m = 1$
$[0,0]$ / $[1,1]$16 / 17$m = 0$
$[3,4]$10$m = 4$
$[3,3]$ / $[4,4]$20 / 21$m = 3$
$[6,7]$12$m = 7$
$[6,6]$ / $[7,7]$24 / 25$m = 6$

最大下标是 25，所以数组至少要 26 个格子。而 $2n = 22$——开 $2n$ 会直接越界。这就是"$2n$ 不够"的具体证据，$n = 11$ 就能撞上。

$4n$ 从哪来？树高是 ⌈log⁡2n⌉\lceil\log_2 n\rceil，堆式下标最大不超过 2⌈log⁡2n⌉+1−12^{\lceil\log_2 n\rceil + 1} - 1；又因为 2⌈log⁡2n⌉<2n2^{\lceil\log_2 n\rceil} < 2n，所以最大下标 $< 4n$。$n = 11$ 时这个上界是 25−1=31<442^5 - 1 = 31 < 44，实际 25，界是松的但安全。

该记住的是：$4n$ 不是节点数，是下标空间的浪费。 想省掉这一半，就得换掉堆式编号——非递归（自底向上）的线段树把叶子对齐到一层，节点严格放在 $[1, 2n)$ 里，数组只要 $2n$；zkw 线段树（张昆玮在《统计的力量》讲稿中系统介绍的写法）走的正是这条路，代价是失去了"当前节点管哪个区间"这个显式信息，写起来更依赖下标技巧。

线段树的变体

持久化线段树（Persistent Segment Tree）：每次更新不修改原节点，而是创建新节点形成新版本，共享未修改的子树。保存历史版本，空间 O(nlog⁡n)O(n \log n)，可回答"第 $k$ 次操作后区间 $[l, r]$ 的和"等历史查询。

合并线段树（Merge Sort Tree）：每个节点存储区间内元素的有序列表，支持区间第 $k$ 小值查询，时间 O(log⁡2n)O(\log^2 n)，空间 O(nlog⁡n)O(n \log n)。

二维线段树：用于矩形区域的查询与更新，时间 O(log⁡2n)O(\log^2 n)，实现复杂。

线段树 + 矩阵乘法：对每个节点存储状态转移矩阵，支持区间线性递推查询（如区间 Fibonacci 数列查询）。

竞技编程中的典型题型

线段树是竞技编程（OI、ICPC、Codeforces、LeetCode Hard）中最常考的数据结构之一：

  • 区间最大值/最小值/和/GCD/XOR
  • 区间加/赋值修改（懒惰传播）
  • 动态开点线段树（状态空间大但实际操作少）
  • 线段树优化建图（竞技图论）
  • 扫描线算法（计算几何，矩形面积并）

现场：什么时候该退回树状数组

如果你的需求只是"单点改 + 区间求和"，线段树几乎总是过度设计。这件事该用树状数组（Fenwick Tree / Binary Indexed Tree），Peter Fenwick 在 1994 年的论文里给出的结构。

它的循环体只有一行：for (; i > 0; i -= i & -i) sum += tree[i];。i & -i 取出 $i$ 最低位的 1，所以每次迭代都消掉一个二进制 1 位——求前缀和 $[1..i]$ 的数组访问次数恰好等于 $i$ 的二进制中 1 的个数（popcount）。

查 $[1..13]$：13=1101213 = 1101_2，访问 tree[13] → tree[12] → tree[8]，三次读，然后 $i$ 归零。同样的前缀和在线段树上要走一条从根到边界的路径并合并沿途节点，量级 log⁡n\log n 但常数是好几倍。

把两者摆在一起：

树状数组线段树
代码量约 10 行递归版 60–100 行，带懒标记 120+ 行
数组大小$n+1$$4n$（堆式下标）
n=106n = 10^6、64 位整数的内存8 MB32 MB
单次前缀查询访问popcount(i)≤log⁡2n\text{popcount}(i) \le \log_2 nO(log⁡n)O(\log n) 个节点，常数更大
支持的聚合需要可逆运算（和、异或）任意可结合运算（和、最值、GCD、矩阵乘）
区间修改需要差分技巧或两个树状数组懒惰传播，直接支持
区间最值做不到（一般情形）天然支持

这张表最该注意的是"支持的聚合"那一行，它划出了真正的分界线。树状数组算区间 $[l,r]$ 靠 pre(r)−pre(l−1)\text{pre}(r) - \text{pre}(l-1)——这一步要求运算有逆元。最大值没有逆元：知道 max⁡(a[1..7])\max(a[1..7]) 和 max⁡(a[1..3])\max(a[1..3])，推不出 max⁡(a[4..7])\max(a[4..7])。所以区间最值只能上线段树。

工程判断：先问"我的聚合运算有没有逆元、我要不要区间修改"，再决定写哪个。 两个答案都是"不需要"的时候，10 行的树状数组能省下的不只是运行时间，更是调试时间——而后者才是竞赛和生产环境里更贵的那个资源。

代价与争议

常数大：相比朴素方案，线段树的常数因子较大（每次操作约 4log⁡n4\log n 次节点访问），对小数据集不如数组。$n$ 只有几十的时候，直接线性扫一段连续内存往往比在树上跳 5 层更快——这条判断和跳表、哈希表在小规模下的表现是同一回事。

实现复杂：递归实现清晰但有栈开销；非递归（自底向上）实现常数更小、数组只要 $2n$，但失去了"当前节点代表哪个区间"的显式信息，写起来更依赖下标技巧。

与树状数组的关系：树状数组是"只做可逆聚合"这一子问题上的极简特例，代码量和内存都小一个量级（详见上一节的对照表）。线段树功能更强，代价是实现和调试成本更高。

缓存不友好：线段树的内存访问模式不够连续，在现代 CPU 上缓存命中率不如数组。B-tree 等缓存友好的结构在数据库中更常用。

"区间取最值"这类操作长期没有好办法——直到一套后来在英文社区被叫做 Segment Tree Beats 的技术出现。它源自中国信息学奥赛国家队候选人的研究报告制度（每位候选人要提交一篇算法研究报告，成绩计入选拔），由选手 jiry_2（吉如一）在 2016 年前后系统化，中文圈也称"吉司机线段树"。核心想法是每个节点额外维护"最大值、次大值、最大值出现次数"，让 chmin(l, r, v)（把区间内所有大于 $v$ 的数改成 $v$）在多数情况下能在某个节点就地终止而不必递归到底。它的代价分析用的是势能函数（potential function），得到的是摊还界而非最坏界——这一点很关键：单次操作可以退化得很难看，只有一整批操作放在一起才便宜。这类"摊还界看起来不像最坏界"的结构在竞赛圈流行，在生产系统里却很少见，因为线上服务关心的往往是尾延迟，而摊还分析恰恰不保证尾延迟。

跨域连接

  • 群：能挂上这棵树的运算由代数性质决定。区间查询只要求可结合，而用前缀相减的做法额外要求可逆——最大值没有逆元，所以前缀法算不了区间最值，只能上线段树。懒惰标记还多一条要求：两次修改必须能复合成一个标记，否则延迟执行不成立。
  • 堆与优先队列：两者都是数组上的树，维护的东西却不同：堆只保证全局最值随时可取，线段树保证任意区间的聚合随时可查。代价换取的能力不同——堆的父子关系只是一个偏序，线段树的每个节点绑定一段确定的区间，正是这份额外结构支撑了区间查询。
  • 二分查找：要找最小的前缀使聚合值超过阈值，通常的做法是外层二分、内层查询。把二分直接嵌进树里可以省掉一层：从根出发看左子树够不够，够就往左，不够就减掉它往右，一趟走到底。这是把搜索结构与索引结构合二为一的典型例子。
  • 计算几何：这个结构的出生地就是几何：扫描线从一侧推进，用它维护当前被覆盖的层数，从而算出矩形并的面积。这里聚合的对象不是数值而是覆盖状态，说明它真正维护的是任意可结合的区间信息，数组求和只是最常见的一个特例。
  • 风险与不确定性：某些高级变体的代价分析给的是摊还界而非最坏界，单次操作可以退化得很难看，只是整批操作平均下来便宜。线上服务关心的恰恰是尾延迟，均值达标而尾部超标是最常见的失败方式——这与只看期望收益、忽略尾部风险是同一个错误。

参考文献

  • Bentley, J. L. Solutions to Klee's Rectangle Problems. Technical report, Carnegie-Mellon University, Pittsburgh, PA, 1977.（线段树的出处）
  • Fenwick, P. M. A New Data Structure for Cumulative Frequency Tables. Software: Practice and Experience 24(3), 327–336 (1994).（树状数组原始论文）

延伸阅读

  • Bentley, J. Programming Pearls. 2nd ed. Addison-Wesley, 2000.（第3章讨论区间查询问题）
  • CP-Algorithms. Segment Tree. https://cp-algorithms.com/datastructures/segmenttree.html（最完整的中英文参考之一）
  • 张昆玮.《统计的力量——线段树全接触》讲稿.（非递归 zkw 线段树的中文原始出处）
  • Codeforces Blog. A simple introduction to "Segment tree beats". （jiry_2 撰写的英文介绍）