线段树(朱全民)

线段树线段树•在一类问题中，我们需要经常处理可以映射在一个坐标轴上的一些固定线段，例如说映射在OX轴上的线段。由于线段是可以互相覆盖的，有时需要动态地取线段的并，例如取得并区间的总长度，或者并区间的个数等等。一个线段是对应于一个区间的，因此线段树也可以叫做区间树。线段树的构造思想•线段树是一棵二叉树，树中的每一个结点表示了一个区间[a,b]。每一个叶子节点表示了一个单位区间。对于每一个非叶结点所表示的结点[a,b]，其左儿子表示的区间为[a,(a+b)/2]，右儿子表示的区间为[(a+b)/2,b]。[1,10][1,5][5,10][1,3][3,5][5,7][7,10][1,2][2,3][3,4][4,5][5,6][6,7][7,8][8,10][8,9][9,10]线段树的运用•线段树的每个节点上往往都增加了一些其他的域。在这些域中保存了某种动态维护的信息，视不同情况而定。这些域使得线段树具有极大的灵活性，可以适应不同的需求。例1•桌子上零散地放着若干个盒子，桌子的后方是一堵墙。如右图所示。现在从桌子的前方射来一束平行光，把盒子的影子投射到了墙上。问影子的总宽度是多少？WallLight分析•这道题目是一个经典的模型。在这里，我们略去某些处理的步骤，直接分析重点问题，可以把题目抽象地描述如下：x轴上有若干条线段，求线段覆盖的总长度。Sum=?最直接的做法•设线段坐标范围为[min,max]。使用一个下标范围为[min,max-1]的一维数组，其中数组的第i个元素表示[i,i+1]的区间。数组元素初始化全部为0。对于每一条区间为[a,b]的线段，将[a,b]内所有对应的数组元素均设为1。最后统计数组中1的个数即可。示例•初始情况•[1，2]•[3，5]•[4，6]•[5，6]00000101101000010111101114个1缺点•此方法的时间复杂度决定于下标范围的平方。•当下标范围很大时（[0,10000]），此方法效率太低。离散化的做法•基本思想：先把所有端点坐标从小到大排序，将坐标值与其序号一一对应。这样便可以将原先的坐标值转化为序号后，对其应用前一种算法，再将最后结果转化回来得解。•该方法对于线段数相对较少的情况有效。示例•[10000,22000][30300,55000][44000,60000][55000,60000]•排序得10000，22000，30300，44000，55000，60000•对应得1，2，3，4，5，6•[1,2][3,5][4,6][5,6]示例•初始情况•[1，2]•[3，5]•[4，6]•[5，6]00000101101000010111101114个1示例•10000，22000，30300，44000，55000，60000•1，2，3，4，5，6•(22000-10000)+(60000-30300)=4170010111123456100002200030300440005500060000缺点•此方法的时间复杂度决定于线段数的平方。•对于线段数较多的情况此方法效率太低。使用线段树的做法•给线段树每个节点增加一个域cover。cover=1表示该结点所对应的区间被完全覆盖，cover=0表示该结点所对应的区间未被完全覆盖。[1,6,0][3,6,0][1,6,0][1,3,0][3,6,0][1,2,0][2,3,0][3,4,0][4,6,0][4,5,0][5,6,0][1,3,0][1,2,1]加入[1,2]加入[3,5][3,4,1][4,6,0][4,5,1][1,2,1][3,4,1][4,5,1]加入[4,6][4,6,1][4,6,1]程序实现线段树的数据结构表示•1、动态数据结构•2、完全二叉树动态数据结构•type•pNode=^TreeNode;•TreeNode=record•b,e:Integer;•l,r:pNode;•cover:Integer;•end;对应区间左右孩子[5,9]完全二叉树[1,9][1,5][1,3][3,5][5,7][7,9][7,8][8,9][5,6][6,7][3,4][4,5][1,2][2,3]完全二叉树•type•TreeNode=record•b,e:Integer;•cover:Integer;•end;对应区间插入算法•procedureInsert(p,a,b:Integer);•var•m:Integer;•begin•ifTree[p].cover=0then•begin•m:=(Tree[p].b+Tree[p].e)div2;•if(a=Tree[p].b)and(b=Tree[p].e)then•Tree[p].cover:=1•elseifb=mthenInsert(p*2,a,b)•elseifa=mthenInsert(p*2+1,a,b)•elsebegin•Insert(p*2,a,m);•Insert(p*2+1,m,b);•end;•end;•end;取中值未被完全覆盖完全覆盖在左边在右边二分统计算法•functionCount(p:Integer):Integer;•begin•ifTree[p].cover=1then•Count:=Tree[p].e–Tree[p].b•elseifTree[p].e–Tree[p].b=1thenCount:=0•elseCount:=Count(p*2)+Count(p*2+1);•end;被完全覆盖是单位区间二分递归求解•事实上，我们也可以不在每个节点中保存其表示范围，而是在递归调用时增加两个参数来加以表示。另一种定义•type•TreeNode=record•cover:Integer;•end;插入算法•procedureInsert(p,l,r,a,b:Integer);•var•m:Integer;•begin•ifTree[p].cover=0then•begin•m:=(l+r)div2;•if(a=l)and(b=r)then•Tree[p].cover:=1•elseifb=mthenInsert(p*2,l,m,a,b)•elseifa=mthenInsert(p*2+1,m,r,a,b)•elsebegin•Insert(p*2,l,m,a,m);•Insert(p*2+1,m,r,m,b);•end;•end;•end;Tree[p].b换成了l，Tree[p].e换成了r，递归时需要多加两个参数，其余都一样统计算法•functionCount(p,l,r:Integer):Integer;•begin•ifTree[p].cover=1then•Count:=r-l•elseifr–l=1thenCount:=0•elseCount:=Count(p*2,l,(l+r)div2)•+Count(p*2+1,(l+r)div2,r);•end;这个也一样例2•桌子上零散地放着若干个盒子，桌子的后方是一堵墙。如右图所示。问从桌子前方可以看到多少个盒子？假设人站得足够远。Wall分析•可以这样来看这道题：x轴上有若干条不同线段，将它们依次染上不同的颜色，问最后能看到多少种不同的颜色？（后染的颜色会覆盖原先的颜色）•我们可以这样规定：x轴初始是颜色0，第一条线段染颜色1，第二条线段染颜色2，以此类推。分析•原先构造线段树的方法不再适用，但是我们可以通过修改线段树的cover域的定义，使得这道题也能用线段树来解。•定义cover如下：cover=-1表示该区间由多种颜色组成。cover=0表示该区间只有一种单一的颜色cover。插入算法•procedureInsert(p,l,r,a,b,c:Integer);•var•m:Integer;•begin•ifTree[p].covercthen•begin•m:=(l+r)div2;•if(a=l)and(b=r)thenTree[p].cover:=c•elsebegin•ifTree[p].cover=0then•begin•Tree[p*2].cover:=Tree[p].cover;•Tree[p*2+1].cover:=Tree[p].cover;•Tree[p].cover:=-1;•end;•ifb=mthenInsert(p*2,l,m,a,b,c)•elseifa=mthenInsert(p*2+1,m,r,a,b,c)•elsebegin•Insert(p*2,l,m,a,m,c);•Insert(p*2+1,m,r,m,b,c);•end;•end;•end;•end;未被完全覆盖或者染色不同为什么？有可能越界吗？统计算法•使用一个数组Flag，初始化为0。遍历线段树，对于每种颜色c对Flag[c]赋值1。最后统计Flag中1的个数即可。（注意颜色0应该排除在外，可以在最后减1）统计算法•procedureCount(p,l,r:Integer);•begin•ifTree[p].cover=0thenFlag[Tree[p].cover]:=1•elseifr–l1then•begin•Count(p*2,l,(l+r)div2);•Count(p*2+1,(l+r)div2,r);•end;•end;例3•把例2稍加改动，规定：线段的颜色可以相同。连续的相同颜色被视作一段。问x轴被分成多少段。分析•仍然定义cover如下：cover=-1表示该区间由多种颜色组成。cover=0表示该区间只有一种单一的颜色cover。插入算法•插入算法不变统计算法•functionCount(p,l,r:Integer;varlc,rc:Integer):Integer;•var•result,tl,tr:Integer;•begin•ifTree[p].cover=0then•begin•lc:=Tree[p].cover;•rc:=Tree[p].cover;•ifTree[p].cover0thenCount:=1•elseCount:=0;•end•elseifr–l1then•begin•result:=Count(p*2,l,(l+r)div2,lc,tl)+Count(p*2+1,(l+r)div2,r,tr,rc);•if(tl=tc)and(tl0)then•result:=result-1;•Count:=result;•end;•end;最左边的颜色最右边的颜色最左颜色=最右颜色=本身非底色则统计数加1连接处颜色相同并且非底色，则总数减1例4•x轴上有若干条不同线段，问某个单位区间[x,x+1]上重叠了多少条线段？分析•为线段树每个节点增加一个Count域。表示所对应区间上重叠的线段数。•思考线段树的构造方法：当某线段能够完整覆盖某个结点所对应的区间时，则不再二分。因此要统计某个单位区间上重叠的线段总数，必须把从叶结点到根结点路径上所有结点的count域累加。插入算法•procedureInsert(p,l,r,a,b:Integer);•var•m:Integer;•begin•m:=(l+r)div2;•if(a=l)and(b=r)thenTree[p].count:=Tree[p].count+1•elsebegin•ifb=mthenInsert(p*2,l,m,a,b)•elseifa=mthenInsert(p*2+1,m,r,a,b)•elsebegin•Insert(p*2,l,m,a,m);•Insert(p*2+1,m,r,m,b);•end;•end;•end;统计算法•functionCount(p:Integer):Integer;•var•result:Integer;•begin•result:=0;•whilep0do•begin•result:=result+Tree[p].count;•p:=pdiv2;•end;•Count:=re