重修数据结构：线段树

发表时间   |   更新时间 | 分类

什么是线段树，为什么要用线段树

首先，我们来回答什么是线段树。顾名思义，线段树就是线段构成的🌲用树结构来表示线段，为什么需要用树来表示线段呢（似乎用数组表示线段已经很科学高效了），因为有时候我们需要频繁地对一个区间进行查询操作。这种时候用线段树会缩减操作的时间复杂度的数量级。

举个🌰：小明有4根冰棍，他给它们编号是$0\sim 3$。每根冰棍都有不同的购买价格，按冰棍的编号依次是$[10,15,20,5]$。现在小明想知道不同编号区间里最贵冰棍的价格，比如：$[0,2]$号最贵冰棍的价格（我们都知道是20）。

对于用数组保存的冰棍价格，他只需要遍历下标$[0,2]$，找出其中最大的数就可以了。这是数组的解法。

那么用线段树怎么寻找最贵的冰棍呢？来考虑线段树（用下图来表示）：

线段树

线段树的节点中保存的不仅仅是这个区间，其中也保存了这个区间里面最贵的冰棍的价格。现在我们想知道$[0,2]$区间最贵的冰棍的价格。

首先从树的根节点$[0,3]$开始找起，$[0,3]$中保存的值是编号$0\sim 3$的冰棍的最贵价格，显然是20（这个20是在构建这棵树的时候就已经算得并且保存进去的，下文中会阐述如何计算），但是这个20并不是我们想知道的答案，为什么呢，因为编号$0\sim 3$号冰棍的最贵价格是20，并不能说明$0\sim 2$号冰棍的最贵价格也是20——有可能3号冰棍的价格是20，此时我们的计算结果就是不正确的，这个很好理解。所以从根节点中找不到我们想要的答案，我们继续往下搜索：

先考虑左子节点表示的区间$[0,1]$，这个区间是在我们要找的区间$[0,2]$之内的，所以前者的最贵价格一定可以给我们的答案提供一个参考，我们记录这个结果：$[0,1]$区间的最贵价格是15。

继续考虑$[0,3]$的右子节点，表示的区间是$[2,3]$。和上面的分析相同，这个节点中的结果不能表征$[0,2]$的冰棍（因为3号冰棍还在里面呢），我们继续向下寻找。此时$[2,3]$的左子节点表示的区间是$[2,2]$，它其实是一个叶子节点，代表了2号冰棍，这个节点中存储的是$[2,2]$区间里的冰棍最贵价格——其实就是2号冰棍的价格，这个区间是在要求的$[0,2]$之内的，我们把这个值记录下来，为最终结果提供参考，这个值是：20。最后，$[2,3]$的右子节点$[3,3]$（也就是3号冰棍）完全不在我们要考虑的区间内，把它抛弃就是了。

最后我们获得了两个信息：区间$[0,1]$的最贵价格是15，以及区间$[2,2]$的最贵价格是20。我们要求的是区间$[0,2]$的最贵冰棍价格，那取这两个价格中更大的那个就是了，最终我们的结果就是：区间$[0,2]$的冰棍中最贵价格是$\mathrm{max}(15,20)=20$。

从上面的例子可以看出，线段树所需要比较重要的性质就是局部的值会影响全局的值。比如说对于冰棍，我们想要查询的是编号$i$到$j$的最贵冰棍的价格，这样$[i,j]$区间内的值会被其中最贵冰棍的价格所影响，这个最贵价格会被保存在$[i,j]$区间中，这种情况下才适合使用线段树，另外一般还有：求区间的最小值，求区间的和等等。准确而言，线段树解决的问题类型是：一维空间上的几何统计。

线段树的使用

构建一棵线段树

扯了一个我感觉还算过得去的例子后，我们来看看怎么构建一棵线段树

1
2
3
4
5
6
7
8
9
10
11
struct SegmentTreeNode{
    int start, end, max;            // 区间左边界，右边界与[start,end]之间的最大值
    SegmentTreeNode *left, *right;  // 节点的左右子节点
    // 构造函数
    SegmentTreeNode(int start, int end, int max){
        this.start = start;
        this.end = end;
        this.max = max;
        this.left = this.right = null;
    }
}

结构体中定义了这棵树所表示的区间$[\mathrm{start},\mathrm{end}]$以及这个区间中最贵的冰棍的价格$\mathrm{max}$

好了，现在要用给定的数组来初始化这棵线段树，主要体现一种递归的思想

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 主函数：递归创建一棵线段树
SegmentTreeNode build(vector<int> A){
    buildNode()
}

// 递归构建树节点
SegmentTreeNode buildNode(int left, int right, vector<int> &A){
    // 如果超出边界，返回null
    if(left > right) return null;

    // 如果节点有意义，创建根节点，并用区间最左边的值初始化
    SegmentTreeNode root = new SegmentTreeNode(left, right, A[left]);
    // 检验节点是否为叶子节点，若是则直接返回（已经初始化完毕了这个节点的所有属性值）
    if(left == right) return root;

    // 从中间对区间进行切分，递归创建当前节点的左右子节点
    int mid = (left+right)/2;
    root.left = buildNode(left, mid, A);
    root.right = buildNode(mid+1, right, A);
    root.max = max(root.left.max, root.right.max);
}

线段树的更新

在上面，我们已经使用了一个给定的数组$A$初始化了一棵线段树，树节点中的$\mathrm{max}$属性是树节点对应区间中的最大值。

现在的问题是，用来创建线段树的数组$A$发生了改变，怎么更新这棵线段树呢？还是使用递归的方式。具体的，我们从根节点开始一路查询所有包含被更新节点的区间，然后把这些区间里面的值全部更新一遍，由于树深为$\mathrm{log}_2n$，所以更新的时间复杂度是$\mathrm{log}_2n$。

下面是具体的实现代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 传入当前所在的区间，被更改数字在$A$中的下标，以及更改后的数字value
void update(SegmentTreeNode root, int index, int value){
    // 如果这个节点是叶子节点，并且是要修改的结点，就进行修改，并直接返回
    if(root.start==root.end && root.start==index){root.max = value; return;}

    // 开始分割区间，进行递归的修改
    int mid = (root.start+root.end)/2;
    // 被修改的节点在当前区间的左子区间
    if(index <= mid) update(root.left, index, value);
    // 被修改的节点在当前区间的右子区间
    else update(root.right, index, value);

    // 更新当前节点的max值
    root.max = max(root.max, value);
    return;
}

线段树的使用：查询

终于讲到了线段树被使用的最终目的：查询了。正如更新一样，线段树的查询也是沿着一棵树向下查，因此时间复杂度仅仅是$\mathrm{log}_2n$（这也是线段树比数组优越的根本原因！）

查询的区间可能出现一半在左子区间，一半又有部分在右子区间的情况，总之可能正好不被包在一个节点里面，所以我们需要设计递归查找的逻辑

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 线段树的节点，以及待查询的左右子区间
int query(SegmentTreeNode root, int start, int end){
    // 情况1：当前节点区间完全在待查询区间内，它成为待查询结果的一种候选结果，直接返回这个区间
    if(root.start>=start && root.end<=end) return root.max;

    // 对于其他情况，要对线段树进行分割
    int mid = (root.start+root.end)/2;
    int res = INT_MIN;      // 初始化查询结果
    // 要继续向下分割直到待查询区间完全包裹住某一节点为止——最差的情况是只包裹住了叶子节点
    if(mid >= start) res = max(res, query(root.left, start, end));
    if(mid+1 <= end) res = max(res, query(root.right, start, end));
    // 返回查询结果
    return res;
}

线段树编程总结

对上面的内容进行一下实践上的总结。要创建并使用一棵线段树，我们需要编写这些代码：

  1. 建立线段树的结构(struct定义)：即包括左右区间的范围，待统计的值，以及左右子节点的指针
  2. 初始化线段树(init函数)：要根据当前的数组来初始化线段树
  3. 更新线段树(update函数)：当数组可能发生改变时，要编写修改线段树的函数否则不用写这个函数
  4. 最最重要的，对线段树执行查询(query函数)：即对于一个输入的区间，我们要使用线段树来查询这个区间里面的统计值是多少

没那么简单

上面的线段树实现我都用二级标题，肯定不是因为我强迫症发作，而是我在学习线段树资料的时候，看到了网上所流传的清华大学-张昆玮的一份讲述线段树的PPT，其中把线段树的诸般变化和优化讲述的神乎其神。在这里占个坑，待我 有空 仔细研读后再来更新。

Reference

统计的力量-线段树.张昆玮.清华大学 （此处没有超链接请勿点击）