数据结构-讲义-线段树.ppt

线段树,线段树,在一类问题中，我们需要经常处理可以映射在一个坐标轴上的一些固定线段，例如说映射在OX轴上的线段。由于线段是可以互相覆盖的，有时需要动态地取线段的并，例如取得并区间的总长度，或者并区间的个数等等。一个线段是对应于一个区间的，因此线段树也可以叫做区间树。,线段树的构造思想,线段树是一棵二叉树，树中的每一个结点表示了一个区间a,b。每一个叶子节点表示了一个单位区间。对于每一个非叶结点所表示的结点a,b，其左儿子表示的区间为a,(a+b)/2，右儿子表示的区间为(a+b)/2,b。,线段树的运用,线段树的每个节点上往往都增加了一些其他的域。在这些域中保存了某种动态维护的信息，视不同情况而定。这些域使得线段树具有极大的灵活性，可以适应不同的需求。,例1,桌子上零散地放着若干个盒子，桌子的后方是一堵墙。如右图所示。现在从桌子的前方射来一束平行光，把盒子的影子投射到了墙上。问影子的总宽度是多少？,分析,这道题目是一个经典的模型。在这里，我们略去某些处理的步骤，直接分析重点问题，可以把题目抽象地描述如下：x轴上有若干条线段，求线段覆盖的总长度。,最直接的做法,设线段坐标范围为min,max。使用一个下标范围为min,max-1的一维数组，其中数组的第i个元素表示i,i+1的区间。数组元素初始化全部为0。对于每一条区间为a,b的线段，将a,b内所有对应的数组元素均设为1。最后统计数组中1的个数即可。,示例,初始情况1，23，54，65，6,4个1,缺点,此方法的时间复杂度决定于下标范围的平方。当下标范围很大时（0,10000），此方法效率太低。,离散化的做法,基本思想：先把所有端点坐标从小到大排序，将坐标值与其序号一一对应。这样便可以将原先的坐标值转化为序号后，对其应用前一种算法，再将最后结果转化回来得解。该方法对于线段数相对较少的情况有效。,示例,10000,2200030300,5500044000,6000055000,60000排序得10000，22000，30300，44000，55000，60000对应得1，2，3，4，5，61,23,54,65,6,示例,初始情况1，23，54，65，6,4个1,示例,10000，22000，30300，44000，55000，600001，2，3，4，5，6(22000-10000)+(60000-30300)=41700,123456,100002200030300440005500060000,缺点,此方法的时间复杂度决定于线段数的平方。对于线段数较多的情况此方法效率太低。,使用线段树的做法,给线段树每个节点增加一个域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、完全二叉树,动态数据结构,typepNode=TreeNode;TreeNode=recordb,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,完全二叉树,typeTreeNode=recordb,e:Integer;cover:Integer;end;,对应区间,插入算法,procedureInsert(p,a,b:Integer);varm:Integer;beginifTreep.cover=0thenbeginm:=(Treep.b+Treep.e)div2;if(a=Treep.b)and(b=Treep.e)thenTreep.cover:=1elseifb=mthenInsert(p*2+1,a,b)elsebeginInsert(p*2,a,m);Insert(p*2+1,m,b);end;end;end;,取中值,未被完全覆盖,完全覆盖,在左边,在右边,二分,统计算法,functionCount(p:Integer):Integer;beginifTreep.cover=1thenCount:=Treep.eTreep.belseifTreep.eTreep.b=1thenCount:=0elseCount:=Count(p*2)+Count(p*2+1);end;,被完全覆盖,是单位区间,二分递归求解,事实上，我们也可以不在每个节点中保存其表示范围，而是在递归调用时增加两个参数来加以表示。,另一种定义,typeTreeNode=recordcover:Integer;end;,插入算法,procedureInsert(p,l,r,a,b:Integer);varm:Integer;beginifTreep.cover=0thenbeginm:=(l+r)div2;if(a=l)and(b=r)thenTreep.cover:=1elseifb=mthenInsert(p*2+1,m,r,a,b)elsebeginInsert(p*2,l,m,a,m);Insert(p*2+1,m,r,m,b);end;end;end;,Treep.b换成了l，Treep.e换成了r，递归时需要多加两个参数，其余都一样,统计算法,functionCount(p,l,r:Integer):Integer;beginifTreep.cover=1thenCount:=r-lelseifrl=1thenCount:=0elseCount:=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);varm:Integer;beginifTreep.covercthenbeginm:=(l+r)div2;if(a=l)and(b=r)thenTreep.cover:=celsebeginifTreep.cover=0thenbeginTreep*2.cover:=Treep.cover;,未被完全覆盖或者染色不同,为什么？有可能越界吗？,插入算法,Treep*2+1.cover:=Treep.cover;Treep.cover:=-1;end;ifb=mthenInsert(p*2+1,m,r,a,b,c)elsebeginInsert(p*2,l,m,a,m,c);Insert(p*2+1,m,r,m,b,c);end;end;end;end;,未被完全覆盖或者染色不同,为什么？有可能越界吗？,统计算法,使用一个数组Flag，初始化为0。遍历线段树，对于每种颜色c对Flagc赋值1。最后统计Flag中1的个数即可。（注意颜色0应该排除在外，可以在最后减1）,统计算法,procedureCount(p,l,r:Integer);beginifTreep.cover=0thenFlagTreep.cover:=1elseifrl1thenbeginCount(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;varresult,tl,tr:Integer;beginifTreep.cover=0thenbeginlc:=Treep.cover;rc:=Treep.cover;ifTreep.cover0thenCount:=1elseCount:=0;,最左边的颜色,最右边的颜色,最左颜色=最右颜色=本身非底色则统计数加1,连接处颜色相同并且非底色，则总数减1,统计算法,endelseifrl1thenbeginresult:=Count(p*2,l,(l+r)div2,lc,tl)+Count(p*2+1,(l+r)div2,r,tr,rc);if(tl=tc)and(tl0)thenresult:=result-1;Count:=result;end;end;,最左边的颜色,最右边的颜色,最左颜色=最右颜色=本身非底色则统计数加1,连接处颜色相同并且非底色，则总数减1,例4,x轴上有若干条不同线段，问某个单位区间x,x+1上重叠了多少条线段？,分析,为线段树每个节点增加一个Count域。表示所对应区间上重叠的线段数。思考线段树的构造方法：当某线段能够完整覆盖某个结点所对应的区间时，则不再二分。因此要统计某个单位区间上重叠的线段总数，必须把从叶结点到根结点路径上所有结点的count域累加。,插入算法,procedureInsert(p,l,r,a,b:Integer);varm:Integer;beginm:=(l+r)div2;if(a=l)and(b=r)thenTreep.count:=Treep.count+1elsebeginifb=mthenInsert(p*2+1,m,r,a,b)elsebeginInsert(p*2,l,m,a,m);Insert(p*2+1,m,r,m,b);end;end;end;,统计算法,functionCount(p:Integer):Integer;varresult:Integer;beginresult:=0;whilep0dobeginresult:=result+Treep.count;p:=pdiv2;end;Count:=result;end;,例5,一行N个方格，开始每个格子里的数都是0。现在动态地提出一些问题和修改：提问的形式是求某一个特定的子区间a,b中所有元素的和；修改的规则是指定某一个格子x，加上或者减去一个特定的值A。现在要求你能对每个提问作出正确的回答。1N1024,提问和修改的总数可能达到60000条。,用线段树解,为线段树每个节点增加一个Count域。表示所对应区间内元素之和。每次修改一个格子，需要修改从叶结点到根结点路径上所有结点的值。特别注意：题目中的区间是以元素为端点，因此a,b和b,c存在重合，这和我们之前讨论的区间定义不同。我们这里忽略预处理过程，直接使用之前的区间定义。,abc,定义,typeTreeNode=recordcount:Integer;end;,插入算法,procedureModify(p,delta:Integer);beginrepeatTreep.count:=Treep.count+delta;p:=pdiv2;untilp=0;end;,统计算法,functionCount(p,l,r,a,b:Integer):Integer;varm:Integer;beginif(l=a)and(r=b)thenCount:=Treep.countelsebeginm:=(l+r)div2;ifb=mthenCount:=Count(p*2+1,m,r,a,b)elseCount:=Count(p*2,l,m,a,m)+Count(p*2+1,m,r,m,b);end;end;,介绍另一种算法,对于序列a，我们设一个数组C，定义Ci=ai2k+1+ai，k为i在二进制下末尾0的个数。,图例,(1)10=(0001)2,(2)10=(0010)2,(3)10=(0011)2,(4)10=(0100)2,(5)10=(0101)2,(6)10=(0110)2,(7)10=(0111)2,(9)10=(1001)2,(8)10=(1000)2,如何计算x对应的2k？,2k=xand(xxor(x-1)以6为例(6)10=(0110)2xor6-1=(5)10=(0101)2(0011)2and(6)10=(0110)2(0010)2,k为x在二进制数下末尾0的个数。,functionLowbit(x:Integer):Integer;beginLowbit:=xand(xxor(x1);end;,如何计算某个区间a,b的和sum(a,b),我们这里所说的区间以元素为端点把这个问题转化成为求sum(1,b)-sum(1,a-1)如何求sum(1,x)？,求和算法,functionSum(x:Integer):Integer;varresult:Integer;beginresult:=0;whilex0dobeginresult:=result+Cx;x:=xLowbit(x);end;Sum:=result;end;,如何修改一个元素的值,设要修改的元素是ap任意x满足x=pxLowbit(x)的Cx均要修改。,如何确定哪些Cx需要修改？,修改算法,procedureModify(p,delta:Integer);beginwhilep0dobegint:=y;whilet0dobeginresult:=result+Cx,t;t:=tLowbit(t);end;x:=xLowbit(x);end;Sum:=result;end;,修改算法,procedureModify(x,y,delta:Integer);vart:Integer;beginwhilex=ndobegint:=y;whilet=ndobeginCx,t:=Cx,t+delta;t:=t+Lowbit(t);end;x:=x+Lowbit(p);end;end;,思考,1、能否把这种算法应用到前面的例题上去？2、如果用线段树解Mobile，应该怎么做？,两种算法的比较,线段树对题目的适应性强，但是要求有较高的处理技巧。后一种算法适用类型单一，但是算法巧妙，其效率也比线段树高。,