2.4.1 线段树

1.线段树的概念：

　　线段树是擅长处理区间的，形如下图的数据结构。线段树是一颗完美二叉树（Perfect Binary Tree）,树上的每个节点都维护一个区间。根维护的是整个区间，每个节点维护的是父亲的区间二等分后的其中一个子区间。当有n个元素时，对区间的操作可以在O（log n）的时间内完成。

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??

根据节点中维护的数据的不同，线段树可以提供不同的功能。下面我们以实现了Range Minimum Query（RMQ）操作的线段树为例进行说明。

2.基于线段树的RMQ的结构

下面要建立的线段树在给定数列a0,a1,……,a(n-1)的情况下，可以在O（log n）时间内完成如下两种操作：

（1）给定s和t，求a（s），a（s+1），……，a（t）的最小值

（2）给定 i 和 x，把 ai 的值改成x

如下图，线段树的每个节点维护对应区间的最小值。在建树时，只需要按从下到上的顺序分别取左右儿子的值中较小者就可以了。

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

3.基于线段树的RMQ的查询

如果要求a0，……，a6的最小值。我们只需要求下图中的三个节点的值的最小值即可。

?

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

像这样，即使查询的是一个比较大的区间，由于较靠上的节点对应较大的区间，通过这些区间就可以知道大部分值的最小值，从而只需访问很少的节点就可以求得最小值。

要求某个区间的最小值，像下面这样递归处理就可以了。

　　如果所查询的区间和当前节点对应的区间完全没有交集，那么就返回一个不影响答案的值（例如INT—MAX）。

　　如果所查询的区间完全包含了当前节点对应的区间，那么就返回当前节点的值。

　　以上两种情况都不满足的话，就对两个儿子递归处理，返回两个结果中的较小者。

4.基于线段树的RMQ的值的更新

在更新a0的值时，需要重新计算下图所示的4个节点的值。

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??

在更新ai的值时，需要对包含 i 的所有区间对应的节点的值重新进行计算。在更新时，可以从下面的节点开始向上不断更新，把每个节点的值更新为左右两个儿子的值的较小者就可以了。

5.基于线段树的