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