《线段树课件教学讲义》由会员分享，可在线阅读，更多相关《线段树课件教学讲义（66页珍藏版）》请在金锄头文库上搜索。
1、线段树,线段树,在一类问题中，我们需要经常处理可以映射在一个坐标轴上的一些固定线段，例如说映射在OX轴上的线段。由于线段是可以互相覆盖的，有时需要动态地取线段的并，例如取得并区间的总长度，或者并区间的个数等等。一个线段是对应于一个区间的，因此线段树也可以叫做区间树。,线段树的构造思想,线段树是一棵二叉树，树中的每一个结点表示了一个区间a,b。每一个叶子节点表示了一个单位区间。对于每一个非叶结点所表示的结点a,b，其左儿子表示的区间为a,(a+b)/2，右儿子表示的区间为(a+b)/2,b。,例1,桌子上零散地放着若干个盒子，桌子的后方是一堵墙。如右图所示。现在从桌子的前方射来一束平行光， 把盒
2、子的影子投射到了墙上。问影子的总宽度是多少？,分析,这道题目是一个经典的模型。在这里，我们略去某些处理的步骤，直接分析重点问题，可以把题目抽象地描述如下：x轴上有若干条线段，求线段覆盖的总长度。,最直接的做法,设线段坐标范围为min,max。使用一个下标范围为min,max-1的一维数组，其中数组的第i个元素表示i,i+1的区间。数组元素初始化全部为0。对于每一条区间为a,b的线段，将a,b内所有对应的数组元素均设为1。最后统计数组中1的个数即可。,示例,初始情况 1，2 3，5 4，6 5，6,4个1,缺点,此方法的时间复杂度决定于下标范围的平方。 当下标范围很大时（0,10000），此方法
3、效率太低。,离散化的做法,基本思想：先把所有端点坐标从小到大排序，将坐标值与其序号一一对应。这样便可以将原先的坐标值转化为序号后，对其应用前一种算法，再将最后结果转化回来得解。 该方法对于线段数相对较少的情况有效。,示例,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,4个1,示例,10000，22000，30300，44000，55000，60000
4、 1 ，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,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,加入
5、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
6、, 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); Ins
7、ert(p * 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;,被完全覆盖,是单位区间,二分递归求解,事实上，我们也可以不在每个节点中保存其表示范围，
8、而是在递归调用时增加两个参数来加以表示。,另一种定义,type TreeNode = 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 Inser
9、t(p * 2, l, m, a, m); Insert(p * 2 + 1, m, r, m, b); end; end; end;,Treep.b换成了l，Treep.e换成了r，递归时需要多加两个参数，其余都一样,统计算法,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, (
10、l + r) div 2, r); end;,这个也一样,例2,桌子上零散地放着若干个盒子，桌子的后方是一堵墙。如右图所示。问从桌子前方可以看到多少个盒子？假设人站得足够远。,Wall,分析,可以这样来看这道题：x轴上有若干条不同线段，将它们依次染上不同的颜色，问最后能看到多少种不同的颜色？（后染的颜色会覆盖原先的颜色） 我们可以这样规定：x轴初始是颜色0，第一条线段染颜色1，第二条线段染颜色2，以此类推。,分析,原先构造线段树的方法不再适用，但是我们可以通过修改线段树的cover域的定义，使得这道题也能用线段树来解。 定义cover如下：cover=-1表示该区间由多种颜色组成。cover=
11、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) and (b = r) then Treep.cover := c else begin if Treep.cover = 0 then begin Treep * 2.cover := Treep.cover;,未被完全覆盖或者染色不同,为什么？ 有可能越界吗？,插入算法,Treep * 2
12、 + 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;,未被完全覆盖或者染色不同,为什么？ 有可能越界吗？,统计算法,使用一个数组Flag，初始化为0。遍历线段树，对于每种颜色c对Flagc赋值1。最后统计Flag中1的个数即可。（注意颜色0应该排除在外，可以在最后减1
13、）,统计算法,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轴被分成多少段。,分析,仍然定义cover如下：cover=-1表示该区间由多种颜色组成。cover=0表示该区间只有一种单一的颜
14、色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;,最左边的颜色,最右边的颜色,最左颜色=最右颜色=本身 非底色则统计数加1,连接处颜色相同并且非底色，则总数减1,统计
15、算法,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上重叠了多少条线段？,分析,为线段树每个节点增加一个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)
