不查不知道,一查吓一跳,“线段树”这个名字的定义真是混乱到一定程度了。

维基百科 Segment Tree 说它是一种数据结构,用来存储区间或线段,用来在 O(log n) 的时间内查找包含某个点的所有区间。一般线段树是静态的结构,不需要修改的,但一些教程又很强调线段树的修改,比如说“lazy 节点是线段树的精髓“。与此同时,另一种结构区间树(Interval Tree) 在结构和功能上和线段树又十分接近。看来看去,线段树,区间树在维基百科、教材、博客里的介绍经常大不相同。

本文里,我们以解决区间最小值(RMQ)问题中使用的数据结构为基准,讲讲“线段树”的基本思想。

开始前先申明博主是不搞 ACM 的,因此平时也接触不到这些高级的数据结构。但在学习时看网上的教程也是一头雾水,也因此才想记录自己的学习所得。如有不当之处,请批评指正。

#引子

首先我们考虑一个数组 A,我们要求 $Q(i, j) = min(A_i, A_{i+1}, …, A_j)$。即 A[i], ... A[j] 中的最小值。如果只求一次,那自然是遍历一次,花费 $O(n)$ 时间。如果这个查询很频繁,那很自然地想到先做个索引。

最简单直观的方式是建一个表 index,有 index[i][j] = Q(i,j),例如

A = [1, 3, 2, 3]

j0 1 2 3
i┌──────────
0│1 1 1 1
1│ 3 2 2
2│ 2 2
3│ 3

很 Naive 的建表需要 $O(n^3)$ 时间。如果注意到 dp[i][j] = min(dp[i+1][j], A[i]) 则只需要 $O(n^2)$ 的时间。现在考虑 A[i] 元素发生变化,则需要 $O(n^2)$ 时间更新。

现在考虑更新和查询操作各占 50%,这种建立索引的方式就变得不太合适,于是我们想到了树结构。

#线段树

RMQ 问题代表的是一类“区间查询”的问题,即我们需要对 A[i], ... A[j] 作一些统计,上面的例子里我们想求最小值,常见的还有求最大值,求和,求积,等等。而线段树给我们提供了一种比较通用的索引方式,来加快查询的速度。

我们说“线段树”是索引,也就是说它的作用是对某些数据进行预处理。这一点很重要,我认为理解线段树的重点就在于理解它是如何对原数据进行索引的。

有数组: A = [0,5,2,5,4,3,1,6,3],也就是说原数据是 9 个离散的点(实际可以扩展成连续的类型)。现在我们为这个数组构建“线段树”。树的每个节点包含两种数据,一是区间 [i, j],另一个是该区间里问题的解,这里存放的是 Q(i, j) 值。于是创建线段树如下:

(1)
[0,15]
0
┌───────────────┴───────────────┐
[0,7] [8,15]
0 3
┌───────┴───────┐ ┌───────┴───────┐
[0,3] [4,7] [8,11]
0 1 3
┌───┴───┐ ┌───┴───┐ ┌───┴───┐ ┌───┴───┐
[0,1] [2,3] [4,5] [6,7] [8,9]
0 2 3 1 3
┌─┴─┐ ┌─┴─┐ ┌─┴─┐ ┌─┴─┐ ┌─┴─┐ ┌─┴─┐ ┌─┴─┐ ┌─┴─┐
0 5 2 5 4 3 1 6 3
┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5

上面的树是自底向上创建的,我们添加了许多空节点来让树达到满二叉树,这种树的好处是节点不需要真正存放 [i,j],如果我们对所有节点编号,那么每个节点对应的区间其实可以直接由它的编号得到,当然具体的对应关系和编号的方法有关。同时这种树存放在数组里特别方便。另一种自上而下的方法是:

(2)
[0,8]
0
┌───────────────┴───────────────┐
[0,4] [5,8]
0 1
┌───────┴───────┐ ┌───────┴───────┐
[0,2] [3,4] [5,6] [7,8]
0 4 1 3
┌───┴───┐ ┌───┴───┐ ┌───┴───┐ ┌───┴───┐
[0,1] [2,2] [3,3] [4,4] [5,5] [6,6] [7,7] [8,8]
0 2 5 4 3 1 6 3
┌─┴─┐
[0,0] [1,1]
0 5

#查询

有了上面的树,我们要回答 $Q(i,j)$ 是多少。例如我们问 Q(3,5),纵观全局,我们发现其实 [3,5] 在树中没有对应的节点,但我们可以一步步查询求得:

  1. [0,8]: 输入 [3,5]。发现 [3,5] 被包含在 [0,8] 之中,通过计算我们发现 [3,5] 横跨 [0,4][5,8],因此我们递归求 min(Q(3,4), Q(5,5))
  2. [0,4]:输入 [3,4],发现它完全在 [0,4] 的右子树,于是向右子树查询 [3,4]
  3. [3,4]:输入 [3,4] 与自己完全重合,于是返回保存的值 4
  4. [5,8]:输入 [5,5],向左子树查询
  5. [5,6]:输入 [5,5],向左子树查询
  6. [5,5]:输入 [5,5],与自己完全重合,返回保存的值 3
  7. [0,8]:返回 min(4, 3) = 3

上面的描述比较啰唆,主要是因为算法本身就是递归的过程。写成代码如下:

def search(root, i, j):
if root.left == i and root.rigth == j:
return root.value

mid = (root.left + root.right) // 2
if j <= mid:
return search(root.left, i, j)
elif i >= mid + 1:
return search(root.right, i, j)
else:
return min(search(root.left_child, i, mid), search(root.right_child, mid+1, j))

这个算法的时间复杂度是 $O(\log n)$。虽然代码看上去需要访问整棵树的所有节点,但实际上,在线段树的每一层,至多只有两个节点需要继续向下求值。这里不严格证明,直观上,如果在某一层有三个节点 A, B, C 需要继续向下求值,设 B = [b, b'] 是这三个节点的中间节点,而 B 的输入是 [x, x'],我们可以推出 b == x and b' == x'。否则最开始的输入不可能是一个区间。

例如我们求 Q(2,5),当访问节点 [0,2] 输入为 (2,2) 我们记为 [0,2]: (2,2)。在第 2 层时需要访问 [0,2]: (2,2), [3,4]: (3,4), [5,6]: (5,5)。可以看见中间节点 [3,4]: (3,4) 是可以直接返回的,不需要再继续向下求值,而 [0,2]: (2,2)[5,6]: (5,5) 是需要继续向下求值的。

0│                               [0,8]
│ 0
│ ┌───────────────┴───────────────┐
1│ [0,4] [5,8]
│ 0 1
│ ┌───────┴───────┐ ┌───────┴───────┐
2│ [0,2] [3,4] [5,6] [7,8]
│ 0 4 1 3
│ ┌───┴───┐ ┌───┴───┐ ┌───┴───┐ ┌───┴───┐
3│ [0,1] [2,2] [3,3] [4,4] [5,5] [6,6] [7,7] [8,8]
│ 0 2 5 4 3 1 6 3
│ ┌─┴─┐
4│[0,0] [1,1]
│ 0 5

#更新

这里更新不讲那些有的没的,复杂的操作。只说“显而易见”,一个底部节点的修改只影响该节点及所有父/祖父节点,因此是 $O(\log n)$。

#构建

构建的算法其实也没啥说的,例如自底向上一个个创建父节点,每个都需要 O(1),而共有 O(n) 个父节点,所以也是 O(n) 的时间。

#结语

我认为线段树的本质,就是用这种“二进制”(二分)的方式去组织(统计)信息。我们可以看到:

  1. 线段树的每个节点保存了部分信息,即某个子区间的解
  2. 对任意输入,我们通过 $O(\log n)$ 个结点就可以组合得到最终的结果
  3. 而理论上组合 $O(\log n)$ 个节点的过程需要是 $O(n)$ 的时间,比如上面提到的 min, max, sum, ... 操作,都是 $O(n)$ 复杂度的。

这又让我想起了以前见过的一道面试题,1000 个瓶子里只有一瓶是毒药,毒要一星期才发作,要在一星期内找出哪瓶有毒,需要多少只老鼠。其本质也是利用二进制的方式去统计信息。(当然并不是二叉树)

知道了这一点之后,相信即使之后看见更复杂的树结构,也能更好地去理解了吧。

#参考资料