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