在一类问题中,我们需要经常处理可以映射在一个坐标轴上的一些固定线段,例如说映射在OX轴上的线段. 由于线段是可以互相覆盖的,有时需要动态地取线段的并,例如取得并区间的总长度,或者并区间的个数等等. 一个线段是对应于一个区间的,因此线段树也可以叫做区间树.
         从简单说起，线段树其实可以理解成一种特殊的二叉树。但是这种二叉树较为平衡，和静态二叉树一样，都是提前已经建立好的树形结构。针对性强，所以效率要高。这里又想到了一句题外话：动态和静态的差别。动态结构较为灵活，但是速度较慢；静态结构节省内存，速度较快。

线段树的构造思想

       线段树处理的是一定的固定线段,或者说这些线段是可以对应于有限个固定端点的. 处理问题的时候,首先抽象出区间的端点,例如说N个端点ti(1≤i≤N). 那么对于任何一个要处理的线段(区间)[a,b]来说,总可以找到相应的i,j,使得ti=a,tj=b,1≤i≤j≤N. 这样的转换就使得线段树上的区间表示为整数,通过映射转换,可以使得原问题实数个区间得到同样的处理. 下图显示了一个能够表示[1,10]的线段树:

                线段树是一棵二叉树,树中的每一个结点表示了一个区间[a,b]. 每一个叶子节点上a+1=b,这表示了一个初等区间. 对于每一个内部结点b-a>1,设根为[a,b]的线段树为T(a,b),则进一步将此线段树分为左子树T(a,(a+b)/2),以及右子树T((a+b)/2,b),直到分裂为一个初等区间为止.

       线段树的平分构造,实际上是用了二分的方法. 线段树是平衡树,它的深度为log(b-a).

接着回到线段树上来，线段树是建立在线段的基础上，每个结点都代表了一条线段[a , b]。长度为1的线段成为元线段。非元线段都有两个子结点，左结点代表的线段为[a , (a + b ) / 2]，右结点代表的线段为[( a + b ) / 2 , b]。

图一就是一棵长度范围为[1 , 10]的线段树。

长度范围为[1 , L] 的一棵线段树的深度为log ( L - 1 ) + 1。这个显然，而且存储一棵线段树的空间复杂度为O（L）。

线段树支持最基本的操作为插入和删除一条线段。下面已插入为例，详细叙述，删除类似。

将一条线段[a , b] 插入到代表线段[l , r]的结点p中，如果p不是元线段，那么令mid＝（l＋r）/2。如果a<mid，那么将线段[a , b] 也插入到p的左儿子结点中，如果b>mid，那么将线段[a , b] 也插入到p的右儿子结点中。

插入（删除）操作的时间复杂度为O （ Log n ）。

上面的都是些基本的线段树结构，但只有这些并不能做什么，就好比一个程序有输入没输出，根本没有任何用处。

最简单的应用就是记录线段有否被覆盖，并随时查询当前被覆盖线段的总长度。那么此时可以在结点结构中加入一个变量int count；代表当前结点代表的子树中被覆盖的线段长度和。这样就要在插入（删除）当中维护这个count值，于是当前的覆盖总值就是根节点的count值了。

另外也可以将count换成bool cover；支持查找一个结点或线段是否被覆盖。

给出在线段[0,8000]上的若干次涂色，问最后能看见哪些颜色，并统计能看到多少段。

就这个题目而言，方法很多，而且数据范围不大，但我们由线段树的角度来解决这个问题。

建立一棵代表线段[0,8000]的线段树，涂色操作就是将[a , b]涂成颜色c。最后做统计。

结构如下：

struct TNode {

        int     left , right;

        int     col;

        TNode   *LeftChild , *RightChild;

};

col 有几种情况，如果col为－1，代表了尚未涂色，－2代表了是混和色，就是说这条线段并不是单一的颜色。其他情况，便是这条线段都是这个颜色的了。

基本的线段树代表的是线段，如果我们把线段离散成点来看，那么线段树可以变化成一种离散类型线段树。

这里可以有两种理解。一种离散关系可以是连续的线段的点，比方说在一条直线上放置的连续小球的着色问题；另一种则是完全将线段离散化分成若干小段，对每一段小段做为元线段来建立线段树，这种线段树可以支持实数划分类型的线段。

Andy想要得到一组数中的最大值。会有一系列的操作Sorter(i[1], j[1]), ..., Sorter(i[k], j[k])。作用是将数组中的第i[k]个数字到第j[k]个数字排序。按照输入给出的顺序，你可以选择要不要执行这个操作。问题是最少需要多少步操作，可以求出这个最大值。题目保证可以求出。

多组数据。

第一行为两个数字N，M。表示N个数，M个操作。

接下来M行，每行描述一个操作i[k] , j [k]。

对于每组数据，输出最少需要多少次操作分离得到最大值。

每组数据一行。

由于要将最大的数字分离到最后的一位，如果我们考虑将数组看成一条[1,n]的线段，而每项操作也看成是从[i[k],j[k]]的线段，那么就是要求按照输入的顺序，将线段[1,n]从左到右依次覆盖掉，问题变成求最小的覆盖线段总数。

考虑最基本的规划方法，用Opt [k] 表示覆盖掉 [1,k]的线段最少需要的步数，那么状态转移方程为：

Opt [k] = min { Opt [d] + 1 | j [p] = k && d >= i [p] && d <= j [p] && k > 1 }

Opt [1] = 0;

最后的答案就是Opt [n]了，但是考虑时间复杂度，是O（m^2）级别的，m最大为500000，超时无疑。但是这里我们看到了规划的决策集合是一条连续的线段，是要在这条线段上面取得最小值，那么线段树的结构就正好适合在这里应用了。

由于这里最小的单位是一个点，所以我们采取线段树的第一种变化，把元线段设置为单位点，即[k,k]。在规划的时候维护线段树即可。

线段树结点结构中，需要加入的元素是int minstep 代表最少需要用到的覆盖线段数目可以覆盖到当前结点所代表的线段中。

给出一个大小为n的数组A[]，给出m个问题（1 <= n <= 100 000, 1 <= m <= 5 000）。问题格式为Q（i，j，k），询问从A[i]到A[j]第k大的元素是什么。A[]中的数各不相同。

在结构上对线段树进行改变，可以得到线段树的另一种变化。

用O（n）的一维数组构造出线段树，无其他附加空间。比方说，一棵从[0,L]的线段树表示为TNode Tree[L];

这里应用二进制将树进行划分。将整数R的二进制表示中的最后一个1换成0，得到数L。Tree[R]代表的线段就是[L,R]。例如：6的二进制表示为（110）₂将最后一个1换成0即为（100）₂＝4，所以Tree[6]代表的线段就是[4,6]。

析出数R的最后一位1的方法是：LowBit（R）＝R^~R。

包含点L的一系列数为x1,x2,……，这里x1=R，x2=x1+LowBit (x1)，x3=x2+LowBit(x2)，……

这种线段树的优点在于：

1． 节省空间。完全线段长度的空间，无需左右指针，无需左右范围。

2． 线段树查找严格log(R)，因为二进制的每位查找一遍。

3． 状态转移快，操作简单。

4． 扩展到多维较为容易。

缺点：

1．随意表示线段[a,b]较为困难。

这种线段树适用于：

1． 查找线段[0,L]的信息。