资源描述：
《论文国家队林涛》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、[1,3][3,5][5,7][7,10][1,2][2,3][3,4][4,5][5,6][6,7][7,8][8,10]线段树的应用广西柳铁一中林涛【摘要】在竞赛解题屮，常遇到与区间有关的操作，比如统计若干矩形并的面积，记录一个区间的最值、总量，并在区间的插入、删除和修改屮维护这些最值、总量。线段树拥有良好的树形二分结构，能够高效的完成这些操作，本文将介绍线段树的各种操作以及一些推广。本文通过3个例了：《蛇》、《空心长方体》、《战场统计系统》，讲述线段树屮基木的插入、删除、查找操作，和不规则的修改和删除操作，以及到二维的推广。关键字：线段树二分子树收缩叶子释放面积树
2、【正文】1.线段树的定义及特征定义1：线段树一棵二叉树，记为T(q0),参数a,b表示该节点表示区间[a,b]o区间的长度b-a记为厶。递归定义T[a,b]：若L>:[a,(a+h)div2]为T的左儿子[(a+b)div29b]为T的右儿了。若L=i:T为一个叶子节点。表示区间[1,10]的线段树表示如F：[1,10][1,5][5,10][8,9][9,10](以下取对数后均向上収整)定理1：线段树把区间上的任意一条线段都分成不超过21ogL条线段证明：(1)在区间0)中,对于线段(c,〃)，如果(c<=a)或(d>=b),那么线段在(a,0)中被分为不超过log
3、(必)。用归纳法证明，如果是单位区间，最多被分为一段，成立。如果区间ab)的左儿子与右儿子成立，那么如果当c<=«时，1.若dv=(°+b)div2那么相当与其左儿子分该线段，所分该线段数树不超过log((a+b)div2・a),即不超过log(fe-a)，成立。1.若d>(a+b)div2那么相当于该线段被分为它左儿子表示的线段，加上右儿子分该线段，线段数不超过l+log(b・@+b)div2),也不超过log(b・a),成立。对于d>=b的情况证明类似，不再赘述。(2)在区间(°0)屮，对于任意线段也用归纳法证明。对于单位区间，最多分为一段，成立。若(a,b)的左儿
4、(与右儿了均成立，则对于线段(c,d)1.若d<=(t/+^)div2则该区间所分该线段等于其左儿子区间所分该线段，线段数小于log((a+fe)div2-a)<21og(&-a),成立。2.若o(a+b)div2则该区间所分该线段等于其右儿子区间所分该线段，线段数小丁log(/?-(6f+/?)div2)<21og(/?-tz),成立。3.若1、2均不成立，则此线段在左儿子区间分该线段满足d>V.Lson.b,分该线段数不超过log(b・(a+b)cliv2),而在右儿子区间分该线段满足CV二V.Rson.a,分该线段不超过log((a+b)div2・1),所以在该区
5、间分该线段不超过21og(bw),成立。这个结论为线段树能在O(logL)的时间内完成一条线段的插入、删除、查找等工作，提供了理论依据。【例题一】蛇I在平面上有N个点，现在要求一些线段，使其满足以下要求：a.这些线段必须闭合b.线段的端点只能是这N个点c.交于一点的两条线段成90度角d.线段都必须平行于坐标轴e.所有线段除在这N个点外不自交f.所有线段的长度之和必须最短如果存在这样的线段，则输出最小长度，否则输出Oo【问题分析】从该题的要求入手，先构岀符合要求的图，再解决线段长度Z和最小的问题。1.题目显然要求一个以给定的N个点为顶点的N多边形。所有线段都要和坐标轴平行
6、，所以每个点只能与上下左右四个点相连。由于与一个点相连的两条线段成90度，每个顶点必须与一条平行于X轴和一条平行于Y轴的线段相连。2.将所有点排序后发现，在同一水平线上的点中，设这些点为Pl,P2,P3,P4……Pn,Pl要有一条平行于X轴的线段与其相连，就必须连它右边的点——P2,而P3如果再连P2,P2就有两条平行于X轴的线段和它相连，所以P3只能连P4,P5只能连P6……，同一垂直线上的点也是如此，所以线段的构造是唯一的，那么最小长度的问题就解决了。3.由于解是唯一的，而是否相连只要广度扩展就可以判断了，所以关键在丁•判断曲上述方法所构出线段是否合法一一满足线段不
7、在N个点之外自交：SaratovStateUniversityProblemArchive,102&Snake.木题考查了基木的插入、删除和查找第■页共9页PlP2P3P4P5P6不相连一不合法不口交一合法口交一不合法图1.合法性判断1.由于所有线段与坐标轴Z—平行，有明显的区间性，可以想到用线段树判断是否自交：(1)由于只可能是与X轴平行的线段和与Y轴的线段相交，所以可以只考虑与Y轴平行的线段是否有线段与Z相交。如果线段(x,y1)・(兀』2)与线段(%1,)，)・(兀2,刃相交，那么应该符合(x1(jlv)yy2),由条
