笔试算法题（42）：线段树（区间树，Interval Tree）

议题：线段树（Interval Tree）

分析：

线段树是一种二叉搜索树，将一个大区间划分成单元区间，每个单元区间对应一个叶子节点；内部节点对应部分区间，如对于一个内部节点[a, b]而言，其左子节点表示的区间为[a, (a+b)/2]，其右子节点表示的区间为[1+(a+b)/2, b]；
对于区间长度为N的线段树，由于其单元节点都是[a, a]的叶子节点，所以其叶子节点数为N，并且整棵树为平衡二叉树，所以总节点数为2N-1，树的深度为log(N)+1；
插入操作：将一条线段[a, b]插入到区间长度为[l, r]的线段树root中，如果root不是单元节点，则求得mid=(l+r)/2；（删除和查找操作类似）

如果b<=mid，则将[a, b]插入到root->left子树中；
如果a=b=mid，则将[a, b]插入到root->left子树中，
如果a=mid<b，则将[a, a]插入到root->left子树中，[a+1, b]插入到root->right子树中；
如果a>mid，则将[a, b]插入到root->right子树中；
如果a<mid<b，则将[a, mid]插入到root->left子树，将[mid+1, b]插入到root->right子树中
线段树最主要的应用是判定几个给定区间之间的关系，判定某一个区间A是否在若干个目标区间内出现，时间复杂度为O(MlogN)，M为A的区间长度，N为构建线段树的整个区间长度；但原始的线段树需要表示每一个单元区间，所以空间复杂度较高为2N，优化方案是离散化（Discretization）压缩线段树区间；但是由于线段树每个节点上需要维护一个int的计数变量（记录其子树被覆盖的次数），所以每次插入或者删除操作都需要O(N)的时间维护线段树的正确性，可以为每一个节点增加一个延迟标记的delta值（Delay Mark），这个值记录当前节点所在的区间需要进行的修改（但是还没有对其左右子树的节点进行修改），当查询路径需要到其左右子树中时，将这个delta 值传递给其左右子树，而将本节点保存饿delta值去除；
一道利用线段树的题目：给定一个自然数集合，自然数的范围是[0,30000]，现在已知N条线段，每条线段以[a,b]的形式给出，现在有M个数字，要求判断每个数字分别在多少条线段上出现过；
一般解法是将M个数字分别于N条线段比较判断，时间复杂度为O(MN)；可以利用线段树记录N条线段在[0, 30000]范围内出现的次数和位置，然后利用二叉树的O(logN)查找时间判断每个数字最终出现的线段；
首先是按照给定的元素范围构建线段树的框架；如给定[0, 7]，则利用线段树为满二叉树的性质，其节点个数为2N-1=15；基本存储结构为数组，如果当前节点为array[i]，则array[2*i]和 array[2*i+1]分别为左右子节点；节点内拥有一个记录本节点代表的线段出现的次数，初始化为0；时间复杂度为O(logK)，K为给定的区间范围；
然后将给定的N条线段插入到已经构建好的线段树框架中；如给定三条线段：[2,5],[4,6],[0,7]，依次插入则最终成为一棵可用的线段树；时间复杂度为O(NlogK)
最后是查询给定的M个点在N条线段出现的次数；如给定数字2，则递归到线段树中的节点[2,2]，并将经过的节点的count值累加起来，最终就是数字2在给定的线段集合内出现的次数；

样例：

  1 /**
  2  * count记录这条线段出现的次数
  3  * */
  4 struct Interval {
  5         int left;
  6         int right;
  7         int count;
  8 };
  9 
 10 /**
 11  * 此函数用于创建线段树的基本结构，InterTree是一个元素为Interval类型的指针数组
 12  * 其大小为2*(max-min+1)，也就是满二叉树；
 13  * */
 14 void ConstructIT(int min, int max, Interval** InterTree, int index) {
 15         /**
 16          * 构建当前节点
 17          * index用于索引InterTree中当前元素的位置
 18          * 遵循父节点为i，则左右子节点分别为2*i, 2*i+1
 19          * */
 20         Interval *temp=new Interval();
 21         temp->count=0;
 22         temp->left=min;
 23         temp->right=max;
 24         InterTree[index]=temp;
 25         /**
 26          * 如果min和max相等，则说明已经到叶子节点
 27          * */
 28         if(min==max)
 29                 return;
 30         /**
 31          * 分别递归创建左右子节点
 32          * */
 33         int middle=(min+max)/2;
 34         ConstructIT(min,middle,InterTree,index*2);
 35         ConstructIT(middle+1,max,InterTree,index*2+1);
 36 }
 37 /**
 38  * 此函数用于注入线段树的线段标记信息
 39  * */
 40 void InsertInfor(int min, int max, Interval** InterTree, int index) {
 41         /**
 42          * 构建线段树的时候，middle本身属于left子树
 43          * */
 44         int middle=(InterTree[index]->left + InterTree[index]->right)/2;
 45 
 46         if(max<=middle) {
 47                 /**
 48                  * 插入线段完全在middle左边
 49                  * */
 50                 InsertInfor(min, max, InterTree, 2*index);
 51         } else if(min>middle) {
 52                 /**
 53                  * 插入线段完全在middle右边
 54                  * */
 55                 InsertInfor(min, max, InterTree, 2*index+1);
 56         } else if(min==InterTree[index]->left &&
 57                         max==InterTree[index]->right) {
 58                 /**
 59                  * 插入线段恰好是节点本身的端点范围，有可能是叶子节点
 60                  * */
 61                 InterTree[index]->count+=1;
 62                 return;
 63         } else if(InterTree[index]->left==InterTree[index]->right) {
 64                 /**
 65                  * 已经到达叶子节点，但是min和max仍旧不等，错误返回
 66                  * */
 67                 return;
 68         } else {
 69                 /**
 70                  * middle将待插入的线段分成两段
 71                  * */
 72                 InsertInfor(min, middle, InterTree, 2*index);
 73                 InsertInfor(middle+1, max, InterTree, 2*index+1);
 74         }
 75 }
 76 /**
 77  * 此函数用于检查覆盖区间，注意此时的min和max可能超出
 78  * InterTree的范围
 79  * */
 80 int CheckInterval(int min, int max, Interval** InterTree, int index) {
 81         int middle=(InterTree[index]->left + InterTree[index]->right)/2;
 82         if(max<middle) {
 83                 return CheckInterval(min, max, InterTree, 2*index);
 84         } else if(min>middle) {
 85                 return CheckInterval(min, max, InterTree, 2*index+1);
 86         } else if(min==InterTree[index]->left &&
 87                         max==InterTree[index]->right) {
 88                         return InterTree[index]->count;
 89         } else {
 90                 return CheckInterval(min, middle, InterTree, 2*index)+
 91                 CheckInterval(middle+1, max, InterTree, 2*index+1);
 92         }
 93 }
 94 
 95 void Crossover(int *first, int lfirst, int *second, int lsecond) {
 96         /**
 97          * 获取first和second数组中各自的最大值与最小值的差值
 98          * 选取差值较小的一个范围作为线段树的构建区间
 99          * 节省空间消耗
100          * */
101         int minf=0, maxf=0,mins=0,maxs=0;
102         for(int i=1;i<lfirst;i+=2) {
103                 if(maxf<first[i])
104                         maxf=first[i];
105                 if(minf>first[i])
106                         minf=first[i];
107         }
108         for(int i=1;i<lsecond;i+=2) {
109                 if(maxs<second[i])
110                         maxs=second[i];
111                 if(mins>second[i])
112                         mins=second[i];
113         }
114         int min=minf,max=maxf;
115         int isFirst=true;
116         if((max-min)>(maxs-mins)) {
117                 min=mins;
118                 max=maxs;
119                 isFirst=false;
120         }
121         /**
122          * 构建一个数组，数组元素为Interval*类型，
123          * 数组大小为线段树节点个数，由于线段树是
124          * 完全二叉树，所以节点数肯定为2N-1，N为区间
125          * 大小，也为叶节点数
126          * */
127         Interval *InterTree[2*(max-min+1)-1];
128         /**
129          * 首先构建线段树的基本结构
130          * */
131         ConstructIT(min, max, InterTree, 0);
132         /**
133          * 然后将线段树范围大小对应的区间数组元素
134          * 插入到线段树中，如果区间在线段树之外则
135          * 需要特殊处理
136          * */
137         int *temp=NULL, length=0;
138         int overlapSize=0;
139         if(isFirst) {
140                 for(int i=1;i<lfirst;i+=2) {
141                         if(first[i]<InterTree[0]->left ||
142                                         first[i-1]>InterTree[0]->right)
143                                 continue;
144                         else if(first[i]==InterTree[0]->left ||
145                                         first[i-1]==InterTree[0]->right)
146                                 overlapSize++;
147                         else
148                                 InsertInfor(first[i-1],first[i], InterTree, 0);
149                 }
150                 temp=second;
151                 length=lsecond;
152         } else {
153                 for(int i=1;i<lsecond;i+=2) {
154                         if(second[i]<InterTree[0]->left ||
155                                         second[i-1]>InterTree[0]->right)
156                                 continue;
157                         else if(second[i]==InterTree[0]->left ||
158                                         second[i-1]==InterTree[0]->right)
159                                 overlapSize++;
160                         else
161                                 InsertInfor(second[i-1],second[i], InterTree, 0);
162                 }
163                 temp=first;
164                 length=lfirst;
165         }
166         /**
167          * 顺序将temp中的区间元素插入到InterTree中
168          * */
169 
170         for(int i=1;i<length;i+=2) {
171                 length+=CheckInterval(temp[i-1],temp[i],InterTree,0);
172         }
173 }

参考连接：
http://hi.baidu.com/alpc62/blog/item/469edeca0043e382c8176875.html