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

《数据结构-讲义-线段树.ppt》由会员分享，可在线阅读，更多相关《数据结构-讲义-线段树.ppt（66页珍藏版）》请在三一办公上搜索。

1、线段树,线段树,在一类问题中，我们需要经常处理可以映射在一个坐标轴上的一些固定线段，例如说映射在OX轴上的线段。由于线段是可以互相覆盖的，有时需要动态地取线段的并，例如取得并区间的总长度，或者并区间的个数等等。一个线段是对应于一个区间的，因此线段树也可以叫做区间树。,线段树的构造思想,线段树是一棵二叉树，树中的每一个结点表示了一个区间a,b。每一个叶子节点表示了一个单位区间。对于每一个非叶结点所表示的结点a,b，其左儿子表示的区间为a,(a+b)/2，右儿子表示的区间为(a+b)/2,b。,线段树的运用,线段树的每个节点上往往都增加了一些其他的域。在这些域中保存了某种动态维护的信息，视不同情况

2、而定。这些域使得线段树具有极大的灵活性，可以适应不同的需求。,例1,桌子上零散地放着若干个盒子，桌子的后方是一堵墙。如右图所示。现在从桌子的前方射来一束平行光，把盒子的影子投射到了墙上。问影子的总宽度是多少？,分析,这道题目是一个经典的模型。在这里，我们略去某些处理的步骤，直接分析重点问题，可以把题目抽象地描述如下：x轴上有若干条线段，求线段覆盖的总长度。,最直接的做法,设线段坐标范围为min,max。使用一个下标范围为min,max-1的一维数组，其中数组的第i个元素表示i,i+1的区间。数组元素初始化全部为0。对于每一条区间为a,b的线段，将a,b内所有对应的数组元素均设为1。最后统计数组

3、中1的个数即可。,示例,初始情况1，23，54，65，6,4个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

4、,6,示例,初始情况1，23，54，65，6,4个1,示例,10000，22000，30300，44000，55000，600001，2，3，4，5，6(22000-10000)+(60000-30300)=41700,1 2 3 4 5 6,10000 22000 30300 44000 55000 60000,缺点,此方法的时间复杂度决定于线段数的平方。对于线段数较多的情况此方法效率太低。,使用线段树的做法,给线段树每个节点增加一个域cover。cover=1表示该结点所对应的区间被完全覆盖，cover=0表示该结点所对应的区间未被完全覆盖。,1,6,0,3,6,0,1,6,0,1,3,0

5、,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

6、,5,1,2,2,3,完全二叉树,typeTreeNode=recordb,e:Integer;cover:Integer;end;,对应区间,插入算法,procedure Insert(p,a,b:Integer);var m:Integer;begin if Treep.cover=0 then begin m:=(Treep.b+Treep.e)div 2;if(a=Treep.b)and(b=Treep.e)then Treep.cover:=1 else if b=m then Insert(p*2+1,a,b)else begin Insert(p*2,a,m);Insert(p*

7、2+1,m,b);end;end;end;,取中值,未被完全覆盖,完全覆盖,在左边,在右边,二分,统计算法,function Count(p:Integer):Integer;begin if Treep.cover=1 then Count:=Treep.e Treep.b else if Treep.e Treep.b=1 then Count:=0 else Count:=Count(p*2)+Count(p*2+1);end;,被完全覆盖,是单位区间,二分递归求解,事实上，我们也可以不在每个节点中保存其表示范围，而是在递归调用时增加两个参数来加以表示。,另一种定义,typeTreeNo

8、de=record cover:Integer;end;,插入算法,procedure Insert(p,l,r,a,b:Integer);var m:Integer;begin if Treep.cover=0 then begin m:=(l+r)div 2;if(a=l)and(b=r)then Treep.cover:=1 else if b=m then Insert(p*2+1,m,r,a,b)else begin Insert(p*2,l,m,a,m);Insert(p*2+1,m,r,m,b);end;end;end;,Treep.b换成了l，Treep.e换成了r，递归时需要

9、多加两个参数，其余都一样,统计算法,function Count(p,l,r:Integer):Integer;begin if Treep.cover=1 then Count:=r-l else if r l=1 then Count:=0 else Count:=Count(p*2,l,(l+r)div 2)+Count(p*2+1,(l+r)div 2,r);end;,这个也一样,例2,桌子上零散地放着若干个盒子，桌子的后方是一堵墙。如右图所示。问从桌子前方可以看到多少个盒子？假设人站得足够远。,Wall,分析,可以这样来看这道题：x轴上有若干条不同线段，将它们依次染上不同的颜色，问最

10、后能看到多少种不同的颜色？（后染的颜色会覆盖原先的颜色）我们可以这样规定：x轴初始是颜色0，第一条线段染颜色1，第二条线段染颜色2，以此类推。,分析,原先构造线段树的方法不再适用，但是我们可以通过修改线段树的cover域的定义，使得这道题也能用线段树来解。定义cover如下：cover=-1表示该区间由多种颜色组成。cover=0表示该区间只有一种单一的颜色cover。,插入算法,procedure Insert(p,l,r,a,b,c:Integer);var m:Integer;begin if Treep.cover c then begin m:=(l+r)div 2;if(a=l)a

11、nd(b=r)then Treep.cover:=c else begin if Treep.cover=0 then begin Treep*2.cover:=Treep.cover;,未被完全覆盖或者染色不同,为什么？有可能越界吗？,插入算法,Treep*2+1.cover:=Treep.cover;Treep.cover:=-1;end;if b=m then Insert(p*2+1,m,r,a,b,c)else begin Insert(p*2,l,m,a,m,c);Insert(p*2+1,m,r,m,b,c);end;end;end;end;,未被完全覆盖或者染色不同,为什么？有

12、可能越界吗？,统计算法,使用一个数组Flag，初始化为0。遍历线段树，对于每种颜色c对Flagc赋值1。最后统计Flag中1的个数即可。（注意颜色0应该排除在外，可以在最后减1）,统计算法,procedure Count(p,l,r:Integer);begin if Treep.cover=0 then FlagTreep.cover:=1 else if r l 1 then begin Count(p*2,l,(l+r)div 2);Count(p*2+1,(l+r)div 2,r);end;end;,例3,把例2稍加改动，规定：线段的颜色可以相同。连续的相同颜色被视作一段。问x轴被分成

13、多少段。,分析,仍然定义cover如下：cover=-1表示该区间由多种颜色组成。cover=0表示该区间只有一种单一的颜色cover。,插入算法,插入算法不变,统计算法,function Count(p,l,r:Integer;var lc,rc:Integer):Integer;var result,tl,tr:Integer;begin if Treep.cover=0 then begin lc:=Treep.cover;rc:=Treep.cover;if Treep.cover 0 then Count:=1 else Count:=0;,最左边的颜色,最右边的颜色,最左颜色=最右

14、颜色=本身非底色则统计数加1,连接处颜色相同并且非底色，则总数减1,统计算法,end else if r l 1 then begin result:=Count(p*2,l,(l+r)div 2,lc,tl)+Count(p*2+1,(l+r)div 2,r,tr,rc);if(tl=tc)and(tl 0)then result:=result-1;Count:=result;end;end;,最左边的颜色,最右边的颜色,最左颜色=最右颜色=本身非底色则统计数加1,连接处颜色相同并且非底色，则总数减1,例4,x轴上有若干条不同线段，问某个单位区间x,x+1上重叠了多少条线段？,分析,为线段

15、树每个节点增加一个Count域。表示所对应区间上重叠的线段数。思考线段树的构造方法：当某线段能够完整覆盖某个结点所对应的区间时，则不再二分。因此要统计某个单位区间上重叠的线段总数，必须把从叶结点到根结点路径上所有结点的count域累加。,插入算法,procedure Insert(p,l,r,a,b:Integer);var m:Integer;begin m:=(l+r)div 2;if(a=l)and(b=r)then Treep.count:=Treep.count+1 else begin if b=m then Insert(p*2+1,m,r,a,b)else begin Inse

16、rt(p*2,l,m,a,m);Insert(p*2+1,m,r,m,b);end;end;end;,统计算法,function Count(p:Integer):Integer;var result:Integer;begin result:=0;while p 0 do begin result:=result+Treep.count;p:=p div 2;end;Count:=result;end;,例5,一行N个方格，开始每个格子里的数都是0。现在动态地提出一些问题和修改：提问的形式是求某一个特定的子区间a,b中所有元素的和；修改的规则是指定某一个格子x，加上或者减去一个特定的值A。现

17、在要求你能对每个提问作出正确的回答。1N1024,提问和修改的总数可能达到60000条。,用线段树解,为线段树每个节点增加一个Count域。表示所对应区间内元素之和。每次修改一个格子，需要修改从叶结点到根结点路径上所有结点的值。特别注意：题目中的区间是以元素为端点，因此a,b和b,c存在重合，这和我们之前讨论的区间定义不同。我们这里忽略预处理过程，直接使用之前的区间定义。,a b c,定义,typeTreeNode=record count:Integer;end;,插入算法,procedure Modify(p,delta:Integer);begin repeat Treep.count:

18、=Treep.count+delta;p:=p div 2;until p=0;end;,统计算法,function Count(p,l,r,a,b:Integer):Integer;var m:Integer;begin if(l=a)and(r=b)then Count:=Treep.count else begin m:=(l+r)div 2;if b=m then Count:=Count(p*2+1,m,r,a,b)else Count:=Count(p*2,l,m,a,m)+Count(p*2+1,m,r,m,b);end;end;,介绍另一种算法,对于序列a，我们设一个数组C，定

19、义Ci=ai 2k+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=x and(x xor(x-1)以6为例(6)10=(0110)2xor 6-1=(5)10=(0101)2(0011)2and(6)10=(0110)2(0010)2,k为x在二进制数下末尾0的个数。,function Lowbit(x:Integ

20、er):Integer;begin Lowbit:=x and(x xor(x 1);end;,如何计算某个区间a,b的和sum(a,b),我们这里所说的区间以元素为端点把这个问题转化成为求sum(1,b)-sum(1,a-1)如何求sum(1,x)？,求和算法,function Sum(x:Integer):Integer;var result:Integer;begin result:=0;while x 0 do begin result:=result+Cx;x:=x Lowbit(x);end;Sum:=result;end;,如何修改一个元素的值,设要修改的元素是ap任意x满足x=

21、pxLowbit(x)的Cx均要修改。,如何确定哪些Cx需要修改？,修改算法,procedure Modify(p,delta:Integer);begin while p=n do begin Cp:=Cp+delta;p:=p+Lowbit(p);end;end;,复杂度分析,很容易得出Sum和Modify的复杂度均为log2n,例6,在一个N*N的方格中，开始每个格子里的数都是0。现在动态地提出一些问题和修改：提问的形式是求某一个特定的子矩阵(x1,y1)-(x2,y2)中所有元素的和；修改的规则是指定某一个格子(x,y)，在(x,y)中的格子元素上加上或者减去一个特定的值A。现在要求你

22、能对每个提问作出正确的回答。1N1024,提问和修改的总数可能达到60000条。,Mobile,例6实际上是例5的推广，从一维扩展到了二维。,求和算法,function Sum(x,y:Integer):Integer;var result,t:Integer;begin result:=0;while x 0 do begin t:=y;while t 0 do begin result:=result+Cx,t;t:=t Lowbit(t);end;x:=x Lowbit(x);end;Sum:=result;end;,修改算法,procedure Modify(x,y,delta:Integer);var t:Integer;begin while x=n do begin t:=y;while t=n do begin Cx,t:=Cx,t+delta;t:=t+Lowbit(t);end;x:=x+Lowbit(p);end;end;,思考,1、能否把这种算法应用到前面的例题上去？2、如果用线段树解Mobile，应该怎么做？,两种算法的比较,线段树对题目的适应性强，但是要求有较高的处理技巧。后一种算法适用类型单一，但是算法巧妙，其效率也比线段树高。,