论文国家队薛矛

《论文国家队薛矛》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、解决动态统计问题的两把利刃剖析线j段树与矩形切ij广东北江中学薛矛【关键字】线段树矩形树方块树线段切割矩形切割【摘要】本文从统计类型的问题出发，以更好地解决这类问题为目的，较详细地介绍了线段树的基木操作，改进和推广；矩形切割的思想以及具体的使用方法。并通过将线段树和矩形切割进行对比，分析了线段树和矩形切割的复朵度，优缺点等,提出了它们各自的适用范围，并总结出何时使用最合适。【目录】一、引言2二、线段树22」线段树的结构22.2线段树的建立32.3线段树中的线段插入和删除32.3.1线段的插入32.3.2线段的删除42.4线段树的简单应用42.5线段树的改进52.6线段树的推广92.7线

2、段树小结10三、矩形切割103.1线段切割103.1.1线段的数据结构113.1.2判断线段和交的两数113.1.3切割线段的过程123.2矩形切割123.3矩形切割的推广133.4矩形切割的应用15四、线段树与矩形切割的比较164.1线段树的时空复杂度174.1.1线段树的空间复杂度174.1.2线段树的时间复杂度174.2矩形切割的时空复杂度174.2.1矩形切割的空间复杂度174.2.2矩形切割的时间复杂度184.3线段树与矩形切割适用范围的比较19五、总结19第1页共31页[1,3][3,5][5,7][7,10][1,2][2,3][3,4][4,5][5,6][6,7][7

3、,8][8,10]【正文】我们在做练习和比赛中，经常能碰见统计类型的题冃。题冃通过输入数据给程序提供事物信息，并要求程序能比较高效地求出某些时刻，某种情况下，事物的状态是怎样的。这类问题往往比较简单明了，也能十分容易地写出模拟程序。但较人的数据规模使得模拟往往不能满足要求。于是我们就要寻找更好的方法。木文将介绍解决此类问题的两种方法——线段树与炬形切割。二、线段树线段树已经不是一个陌生的名词了，相信大家也对线段树比较熟悉，这里只做简要的介绍。2.1线段树的结构线段树是一棵二叉树，其结点是一条“线段”——[a,b],它的左儿子和右儿子分别是这条线段的左半段和右半段,即[a,(a+b)/2

4、」]和[(a+b)/2」,b]°线段树的叶子结点是长度为1的单位线段h,a+l]。下图就是一•棵根为[1,10]的线段树:[1,10][1,5]

5、5,10

6、18,9][9,10]易证一棵以血b]为根的线段树结点数是2*(b-a)-k由于线段树是一棵平衡树，因此一棵以[a,b]为根结点的线段树的深度为log2(2*(b・a))。线段树屮的结点-•般采取如下数据结构：TypeTreeNode=Recorda,b,Left,Right:LongintEnd其屮a,b分别表示线段的左端点和右端点，Left,Right表示左儿子和右儿子的编号。因此我们可以用一个一维数组來表示一棵线段树：Tree

7、:array[1..Maxn]ofTreeNode;a,b,Left,Right这4个域是描述一棵线段树所必须的4个量。根据实际需要,我们可以增加其它的域，例如增加Cover域来计算该线段被覆盖的次数，bj域用来表示结点的修改标记(后而将会提到)等等。/2.2线段树的建立我们可以用一个简单的过程建立一棵线段树。ProcedureMakeTree(a,b)VarNow:LongintBegintot<—tot+1Now<—totTree[Now].a<—aTree[Now].b<—bIfa+1

8、)Tree[Now].Righttot+1MakeTree((a+0)/2」,b)End2.3线段树中的线段插入和删除增加一个Cover的域来计算一条线段被覆盖的次数，即数据结构变为:TypeTreeNode=Recorda,b,Left,Right,Cover:LongintEnd因此在MakeTree的时候应顺便把Cover置0。2.3.1线段的插入插入一条线段[c,d]ProcedureInsert(Num)BeginIf(c

9、Tree[Nitm].a+Insert(Tree[Num].Left)Insert(Tree[Num].Right)End第3页共31页2.3.2线段的删除删除一条线段[c,d]ProcedureDelete(Num)BeginIf(c