资源描述：
《浙江大学 acm程序设计竞赛 培训 线段树课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、线段树浙江大学acm校队线段树在一类问题中，我们需要经常处理可以映射在一个坐标轴上的一些固定线段，例如说映射在OX轴上的线段。由于线段是可以互相覆盖的，有时需要动态地取线段的并，例如取得并区间的总长度，或者并区间的个数等等。一个线段是对应于一个区间的，因此线段树也可以叫做区间树。线段树的构造思想线段树是一棵二叉树，树中的每一个结点表示了一个区间[a,b]。每一个叶子节点表示了一个单位区间。对于每一个非叶结点所表示的结点[a,b]，其左儿子表示的区间为[a,(a+b)/2]，右儿子表示的区间为[(a+b)/2,b]。线段树的运用线
2、段树的每个节点上往往都增加了一些其他的域。在这些域中保存了某种动态维护的信息，视不同情况而定。这些域使得线段树具有极大的灵活性，可以适应不同的需求。例1桌子上零散地放着若干个盒子，桌子的后方是一堵墙。如右图所示。现在从桌子的前方射来一束平行光，把盒子的影子投射到了墙上。问影子的总宽度是多少？WallLight分析这道题目是一个经典的模型。在这里，我们略去某些处理的步骤，直接分析重点问题，可以把题目抽象地描述如下：x轴上有若干条线段，求线段覆盖的总长度。Sum=?最直接的做法设线段坐标范围为[min,max]。使用一个下标范围为[
3、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]），此方法效率太低。离散化的做法基本思想：先把所有端点坐标从小到大排序，将坐标值与其序号一一对应。这样便可以将原先的坐标值转化为序号后，对其
4、应用前一种算法，再将最后结果转化回来得解。该方法对于线段数相对较少的情况有效。示例[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，600001，2，3，4，5，6
5、(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][
6、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
7、][3,4][4,5][1,2][2,3]完全二叉树typeTreeNode=recordb,e:Integer;cover:Integer;end;对应区间插入算法procedureInsert(p,a,b:Integer);varm:Integer;beginifTree[p].cover=0thenbeginm:=(Tree[p].b+Tree[p].e)div2;if(a=Tree[p].b)and(b=Tree[p].e)thenTree[p].cover:=1elseifb<=mthenInsert(p*2,a,b)
8、elseifa>=mthenInsert(p*2+1,a,b)elsebeginInsert(p*2,a,m);Insert(p*2+1,m,b);end;end;end;取中值未被完全覆盖完全覆盖在左边在右边二分统计算法functionCount(p:Inte
