算法导论学习-线段树(1)

1. 线段树简介：

---------------

线段树是建立在线段的基础上，每个结点都代表了一条线段[a,b]。长度为1的线段称为元线段。非元线段都有两个子结点，左结点代表的线段为[a,(a + b) / 2]，右结点代表的线段为[((a + b) / 2）+1,b]。若非元线段的编号为 i，那么他的左孩子编号为 2*i，右孩子为 2*i+1。下图是一棵典型的线段树。，一般的，我们把根节点的编号设为1，那么下图很显然的，[1,5]的编号为2，[6,10]的编号为3，其他节点也以此类推。

2. 线段树有什么用：

-------------------

我么知道一棵线段树上的每个节点都至少有两个域：left 和 right，分别表示一个区间的上限和下限。但是如果只是这样的话，线段树也是中看不中用的。事实上，我们在使用线段树的时候，会视问题的不同给树的节点添加域。在这些域中保存了某种动态维护的信息，这些域使得线段树具有极大的灵活性，可以适应不同的需求。下面举一个例子来看一看线段树的应用：

桌子上零散地（放着若干个木条，桌子的后方是一堵墙。如下图所示（下图把墙虚拟的等分成了8份）。现在从桌子的前方射来一束平行光，把木棍的影子投射到了墙上。求影子的总宽度是多少？（这里假设木棍的长度是正整数，且任一木棍都刚刚好在一些“连续数字对应的墙上”，比如最下方的那根木棍刚好对应了数字2,3,4。）这道题最蛮力的办法是开一个数组，比如就这道题来说，开一个数组A[1,...8]。然后给数组赋初值A[i] = 0, 表示第i段墙没有阴影。然后根据每根木条的阴影的范围修改A数组的值。比如对于最下面的那根木条，A[2]=A[3]=A[4]=1，1表示有阴影。这种方法的时间复杂度为O（n*range）。（n表示木条根数，range表示墙的宽度）

现在我们换用线段树来做，给线段树每个节点增加一个域cover。cover=1表示该结点所对应的区间被完全覆盖，cover=0表示该结点所对应的区间未被完全覆盖。好了，现在线段树节点有3个域：left，right，cover。

###第一步：建立线段树

 1 const int max_size=32010;
 2 struct segmentTree{
 3     int left,right;
 4     int cover;
 5 }a[max_size*3];
 6 int cnt[max_size];
 7 void buildTree(int l,int r,int step){
 8     a[step].left=l;
 9     a[step].right=r;
10     a[step].cover=0;
11     if(l==r) return;
12     int mid=(a[step].left+a[step].right)/2;
13     buildTree(l,mid,step*2);
14     buildTree(mid+1,r,step*2+1);
15 }

###第二步：执行插入动作（我们依次把木条阴影插入到线段树中），代码如下：

 1 void updateSegment(int L,int R,int step){
 2         if(L==a[step].left&&R==a[step].right){
 3             a[step].cover++; return;
 4         }
 5         if(a[step].left==a[step].right) return;
 6         int mid=(a[step].left+a[step].right)/2;
 7         if(R<=mid) updateSegment(L,R,step*2);
 8         else if(L>=mid+1) updateSegment(L,R,step*2+1);
 9         else{
10             updateSegment(L,mid,step*2);
11             updateSegment(mid+1,R,step*2+1);
12         }
13 }

下面四个图分别是依次插入木条[2,4]，插入木条[3,5]，插入木条[4,6]和插入木条[7,7]对应的线段树状态：

###第三步：查询（查询线段树中有阴影部分的长度）

1 int count(int step){
2     if(a[step].cover) return a[step].right-a[step].left+1;
3     if(a[step].left==a[step].right){//leaf node
4         if(a[step].cover) return 1;
5         else return 0;
6     }
7     return count(step*2)+count(step*2+1);
8 }

上图中节点上方标注有cover=1，表示阴影覆盖了该节点表示的区域。根据图（d），我们可以得到最终的阴影长度：[2]*1+[3, 4]*1+[5, 6]*1+[7]*1=1+2*1+2*1+1=6。由于线段树插入，查询操作的耗时为O（lg n），所以时间复杂度有暴力枚举的O(n^2)降低到O(nlgn).

###拓展功能：删除

回到最初的那个状态，如果我们把木条[3,5]拿掉会怎么样？我们发现最终的阴影部分还是6. 。。。下面是删除动作的代码：

 1 void del(int L,int R,int step){
 2     if(L==a[step].left&&R==a[step].right){//fully cover
 3         a[step].cover--; return;
 4     }
 5     if(a[step].left==a[step].right) return;
 6     int mid=(a[step].left+a[step].right)/2;
 7     if(R<=mid) del(L,R,step*2);
 8     else if(L>=mid+1) del(L,R,step*2+1);
 9     else{
10         del(L,mid,step*2);
11         del(mid+1,R,step*2+1);
12     }
13 }

假设我们在已经插入了四根木条的情况下，对应图（d），抽调木条[3,5]，那么线段树的状态转移如下：

以上是线段树的区段动态修改与查询的应用，后续会有线段树的其他应用的介绍，To be continue......