论文--解决动态统计问题的两把利刃-剖析线段树与矩形切割

《论文--解决动态统计问题的两把利刃-剖析线段树与矩形切割》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

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

2、6线段树的推广92.7线段树小结10三、矩形切割103.1线段切割103.1.1线段的数据结构113.1.2判断线段相交的函数113.1.3切割线段的过程113.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【正文】一、引言我们在做练习和比赛中，经常能碰见统计类型的

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

4、位线段[a,a+1]。下图就是一棵根为[1,10]的线段树：易证一棵以[a,b]为根的线段树结点数是2*(b-a)-1。由于线段树是一棵平衡树，因此一棵以[a,b]为根结点的线段树的深度为log2(2*(b-a))。线段树中的结点一般采取如下数据结构：TypeTreeNode=Recorda,b,Left,Right:LongintEnd其中a,b分别表示线段的左端点和右端点，Left，Right表示左儿子和右儿子的编号。因此我们可以用一个一维数组来表示一棵线段树：Tree:array[1..Maxn]ofTreeNode;a,b,Left,Rig

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

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

7、)Ifd>thenInsert(Tree[Num].Right)End2.3.2线段的删除删除一条线段[c,d]ProcedureDelete(Num)BeginIf(cthenDelete(Tree[Num].Right)End2.4线段树的简单应用掌握了线段树的建立，插入和删除这3条操作，就能用线段树解决一些最基本的统计问题了。例如给出

8、一系列线段[a,b](0