ＰＳ：虽然本文有概念上的疏漏，但个人觉得对于线段树讲解的十分透彻，值得仔细品味。
1、概述
线段树，也叫区间树，是一个完全二叉树，它在各个节点保存一条线段（即“子数组”），因而常用于解决数列维护问题，它基本能保证每个操作的复杂度为O(lgN)。
2、线段树基本操作
线段树的基本操作主要包括构造线段树，区间查询和区间修改。
（1） 线段树构造
首先介绍构造线段树的方法：让根节点表示区间[0,N-1]，即所有N个数所组成的一个区间，然后，把区间分成两半，分别由左右子树表示。不难证明，这样的线段树的节点数只有2N-1个，是O(N)级别的，如图：
显然，构造线段树是一个递归的过程，伪代码如下：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
//构造求解区间最小值的线段树function ifv所表示的区间内只有一个元素 v区间的最小值就是这个元素, endif 把v所属的区间一分为二，用w和x两个节点表示。 标记v的左儿子是w，右儿子是x 分别构造以w和以x为根的子树（递归） v区间的最小值end |
线段树除了最后一层外，前面每一层的结点都是满的，因此线段树的深度
h =ceil(log(2n -1))=O(log n)。
（2） 区间查询
区间查询指用户输入一个区间，获取该区间的有关信息，如区间中最大值，最小值，第N大的值等。
比如前面一个图中所示的树，如果询问区间是[0,2]，或者询问的区间是[3,3]，不难直接找到对应的节点回答这一问题。但并不是所有的提问都这么容易回答，比如[0,3]，就没有哪一个节点记录了这个区间的最小值。当然，解决方法也不难找到：把[0,2]和[3,3]两个区间（它们在整数意义上是相连的两个区间）的最小值“合并”起来，也就是求这两个最小值的最小值，就能求出[0,3]范围的最小值。同理，对于其他询问的区间，也都可以找到若干个相连的区间，合并后可以得到询问的区间。
区间查询的伪代码如下：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
|
// |