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

维基百科 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 个瓶子里只有一瓶是毒药，毒要一星期才发作，要在一星期内找出哪瓶有毒，需要多少只老鼠。其本质也是利用二进制的方式去统计信息。（当然并不是二叉树）

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

参考资料