线段树基本知识

  线段树是一颗二叉搜索树，与普通二叉搜索树不同的是，线段树是按照对象的关键码的可能范围来进行划分的。线段树也是按照递归定义的。设一个区间b,e],则：

   1）若b-e==1，那么T(b,e)是叶子节点

   2)如果 b-e>1，那么T(b,(b+e)/2)是左子树，T((b+e)/2,e)是右子树。

如下是一个区间为[1,10]的线段树：

                                       

线段树的基本运算有创建线段树，插入一条线段(一个点)，删除一个线段(一个点)。一般情况下，线段树节点结构中包含一个保存信息的变量c，他可以表示区间覆盖次数，区间中点的个数等等信息。一般情况下，线段树可以用链表或者数组来存储，下面使用的都是数组存储，特别注意的是线段树数组的大小最好开为原来区间的4倍。用stn表示线段树的某个节点，它的区间用[T[stn].b,T[stn].e]来表示，节点信息用T[stn].表示，下面给出线段树一些操作的伪代码：

//创建线段树伪代码
Build(T,b,e){
   T[stn].b=b,T[stn].e=e;
   T[stn].c=0;
   if(b<e){ //如果当前不是叶子节点
        mid=(b+e)/2;
        Build(T,b,mid);
        Build(T,mid+1,e);
 }　

//向线段树中插入一条线段
Insert(T,u,v){
   if(u<=T[stn].b&&v>=T[stn].e)区间覆盖
        T[stn].c++;   //该区间线段覆盖一次
   else{
         mid=(T[stn].b+T[stn].e)/2;
         if(u<=mid) // 与左区间有交集
             Insert(Left[T],u,v);
         if(v>mid)  //与右区间有交集
             Insert(Right[T],u,v);
}

//获取线段长度 
GetLength(T){
      if(T[stn].c>0)
           return T[stn].e-T[stn].b+1;
      else
           return GetLength(Left(T))+GetLength(Right(T));
}

当然，有些区间太大，需要做离散化处理，具体情况具体分析。根据某某大神的博客，它线段树题目类型划分为了5类：

   1.单点更新

   2.成段更新

   3.区间合并

   4.扫描线

   5.其他类型

。。。。。线段树很重要啊，必须通过做大量的题目来掌握！！！