数据结构与算法_线段树

线段树（segment tree）是一种二叉搜索树，也是平衡二叉树，它的每一个结点对应一个区间 [L,R] ,叶子结点对应的区间只有一个结点（L = R）。每一个非叶子结点 [L , R] ，其左孩子区间为 [L, (L+R)/2] ,右孩子区间为 [ (L+R)/2+1, R] 。

    因为线段树是平衡二叉树，所以树高为 log(n)，树上的操作大多和树高有关。线段树主要用于更新和查询，一般至少有一个是区间更新或查询。更新和查新的种类变化多端，灵活运用线段树可以解决多种问题。

    例如，区间最值查询问题（Rang Minimum/Maximum Query, RMQ），该问题有两种操作：(1) 点更新：修改一个元素的值；（2）区间查询：查询一个区间的最值。

1. 线段树的实现

以区间最值查询问题为例，讲述线段的实现过程。

（1）存储方式

    因为要查询区间最大值（最大值或最小值），因此每个结点包含三个域：l, r, mx, 其中 l 和 r 分别表示区间的左右端点， mx表示区间 [ l, r] 的最值。本题以最大值为例。例如，有 10个元素 a[ 1 ... 10] = {5, 3, 7, 2, 12, 1, 6, 4, 8, 15} ,线段树如图所示。

    由于线段树除了最后一层外，其他层构成一个满二叉树，因此可以采用顺序存储方式，用一个数组 tree[ ] 存储结点。如果一个结点的存储下标为 k, 则左孩子的下标为 2k, 右孩子的下标为 2k+1 。 如图所示：

    线段树根节点的存储下标为 1，其左右孩子存储下标分别为 2，3 。。。

(2) 创建线段树

    可以采用递归的方法创建线段树，其创建过程如下：

    1） 如果是叶子结点 （r = l）, 则结点的最值就是对应位置的元素值；

    2） 如果是非叶子结点，递归创建左子树 和右子树；

    3）结点的区间最值等于该结点左右子树最值的最大值；

    代码实现：

（3） 点更新

    点更新是指修改一个元素的值，例如将 a[i] 修改为 v, 仍然采用递归的方法进行点更新，其过程如下：

    1）如果是第 i 个元素所在的叶子结点（r = l 且 l = i）,则修改结点的最值为 v；

    2) 如果是非叶子结点，则判断在左子树中更新还是在右子树中更新;

    3) 返回时更新结点的最值；

    代码实现：

（4）区间查询

    区间查询是指查询一个个区间的最值。仍然采用递归的方法进行区间查询，其过程如下：

    1）如果结点的区间被查询区间 [l, r] 覆盖，则返回该结点的最值；

    2）判断在左子树查询，右子树查询；

    3）返回最值；

（5）区间更新

    对 [l,r] 进行区间更新：

    1) 如果结点的区间被查询区间 [l,r] 覆盖，仅对该结点进行更新，并作懒标记，表示该结点被更新过，对该结点的子结点不再进行更新；

    2）判断在左子树查询，右子树查询。查询过程中，若当前结点带有懒标记，懒标记下传给子结点 (当前结点懒标记清除，子结点更新并做懒标记)，继续查询；

    3）更新最值。

    例如，在[1 , 10] 的线段树中修改 [4,8] 区间的值为 20.

代码实现：

2. 线段树的性能分析：

    线段树采用了分治算法策略，其点更新，区间更新，区间查询均可以在O(log n) 时间内完成。树状数组和线段树都用于频繁的修改和查询问题，树状数组可以实现点更新，区间查询，而线段树还可以实现区间更新，区间查询。线段树的用途更广，更灵活，树状数组比线段树节省空间，代码简单易懂，但是线段树更灵活，凡是能用树状数组的问题一定能用线段树。