从一道题扩展开去-Read.DOC

解决动态统计问题的两把利刃 ——剖析线段树与矩形切割 广东北江中学 薛矛 【】一、引言 2 二、线段树 2 2.1 线段树的结构 2 2.2 线段树的建立 3 2.3 线段树中的线段插入和删除 3 2.3.1 线段的插入 3 2.3.2 线段的删除 4 2.4 线段树的简单应用 4 2.5 线段树的改进 5 2.6 线段树的推广 9 2.7 线段树小结 10 三、矩形切割 10 3.1 线段切割 10 3.1.1 线段的数据结构 11 3.1.2 判断线段相交的函数 11 3.1.3 切割线段的过程 11 3.2 矩形切割 12 3.3 矩形切割的推广 13 3.4 矩形切割的应用 15 四、线段树与矩形切割的比较 16 4.1 线段树的时空复杂度 17 4.1.1 线段树的空间复杂度 17 4.1.2 线段树的时间复杂度 17 4.2矩形切割的时空复杂度 17 4.2.1矩形切割的空间复杂度 17 4.2.2 矩形切割的时间复杂度 18 4.3 线段树与矩形切割适用范围的比较 19 五、总结 19 【正文】 一、引言 我们在做练习和比赛中，经常能碰见统计类型的题目。题目通过输入数据给程序提供事物信息，并要求程序能比较高效地求出某些时刻，某种情况下，事物的状态是怎样的。这类问题往往比较简单明了，也能十分容易地写出模拟程序。但较大的数据规模使得模拟往往不能满足要求。于是我们就要寻找更好的方法。本文将介绍解决此类问题的两种方法——线段树与矩形切割。 二、线段树 线段树已经不是一个陌生的名词了，相信大家也对线段树比较熟悉，这里只做简要的介绍。 2.1 线段树的结构 线段树是一棵二叉树，其结点是一条“线段”——[a,b]，它的左儿子和右儿子分别是这条线段的左半段和右半段，即[a, ]和[,b]线段树的叶子结点是长度为1的单位线段[a,a+1]。下图就是根为[1,10]的线段树： 易证一棵以[a,b]为根的线段树结点数是2*(b-a)-1由于是一棵平衡树，一棵根结点的线段树深度为log2(2*(b-a))。 线段树中的结点一般采取如下数据结构 其中a,b分别表示线段的左端点和右端点，Left，Right表示左儿子和右儿子的编号。因此我们可以用一个一维数组来表示一棵线段树： Tree:array[1..Maxn] of TreeNode; a,b,Left,Right这4个域是描述一棵线段树所必须的4个量。根据实际需要，我们可以增加其它的域，例如增加Cover来计算该线段被覆盖的次数，bj用来表示结点的修改标记（后面将会提到）等等。 2.3 线段树中的线段插入和删除 增加一个Cover的域 因此在MakeTree的时候应顺便把Cover置0。[c,d] 2.3.2 线段的删除 删除一条线段[c,d] 掌握了线段树的建立，插入和删除这3条操作，就能用线段树解决一些最基本的统计问题了。例如给出一系列线段[a,b] (0ab10000)覆盖在数轴上，然后求该数轴上共有多少个单位长度[k,k+1]被覆盖了。我们便可以在读入一系列线段[a,b]的时候，同时调用过程Insert(1)。等所有线段都插入完后，就可以进行统计了： 像这样的基本静态统计问题，线段树是可以很方便快捷地解决的。但是我们会留意到，如果处理一些动态统计问题，比如说一些需要用到删除和修改的统计，困难就出现了。 『例1』在数轴上进行一系列操作。每次操作有两种类型，一种是在线段[a,b]上涂上颜色，另一种将[a,b]上的颜色擦去。问经过一系列的操作后，有多少条单位线段[k,k+1]被涂上了颜色。 这时我们就面临了一个问题——线段的删除。但线段树中线段的删除只能是把已经放的线段删掉，例如我们没有放置[3,6]这条线段，删除[3,6]就是无法做到的了。而这道题目则不同，例如在[1,15]上涂了颜色，我们可以把[4,9]上的颜色擦去，但线段树中只是插入[1,15]这条线段，要删除[4,9]这条线段显然是做不到用回刚刚那个例子。给[1,15]涂上色后，再把[4,9]的颜色擦去。很明显[1,15]这条线段已经不复存在，只剩下[1,4]和[9,15]，所以我们必须对线段树进行修改，才能使它符合改变了的现实。我们不难想到把[1,15]这条线段删去，再插入线段[1,4]和[9,15]。但事实上并非如此简单。如下图 若先前我们已经插入了线段[8,11]，[1,8]。按上面的做法，只把[1,15]删去，然后插入[1,4]，[9,15]的话，[1,8]，[8,11]这两条线段并没有删去，但明显与实际不符了。于是[1,8]，[8,11]也要修改。这时疑问就来了。若以线段[1,15]为根的整