解决动态统计问题的两把利刃----国家集训队2004论文集薛矛

解决动态统计问题的两把利刃——剖析线段树与矩形切割广东北江中学薛矛目录1线段树2矩形切割3线段树与矩形切割的比较4总结※1.1线段树的结构1线段树※1.2线段树的建立ProcedureMakeTree(a,b)VarNow:LongintBegintot←tot+1Now←totTree[Now].a←aTree[Now].b←bIfa+1bthenTree[Now].Left←tot+1MakeTree(a,)Tree[Now].Right←tot+1MakeTree(,b)End2/)(ba2/)(ba线段树是一棵二叉树，线段[a,b]的左右儿子分别为[a,]和[,b]。线段树的叶子结点是长度为1的单位线段[a,a+1]。2/)(ba2/)(ba1线段树※1.3线段的插入和删除可增加一个Cover域来计算一条线段被覆盖的次数：TypeTreeNode=Recorda,b,Left,Right,Cover:LongintEnd插入一条线段[c,d]ProcedureInsert(Num)BeginIf(cTree[Num].a)and(Tree[Num].bd)thenTree[Num].Cover←Tree[Num].Cover+1ElseIfcthenInsert(Tree[Num].Left)IfdthenInsert(Tree[Num].Right)End2/)].[].[(bNumTreeaNumTree2/)].[].[(bNumTreeaNumTree1线段树删除一条线段[c,d]ProcedureDelete(Num)BeginIf(cTree[Num].a)and(Tree[Num].bd)thenTree[Num].Cover←Tree[Num].Cover-1ElseIfcthenDelete(Tree[Num].Left)IfdthenDelete(Tree[Num].Right)End2/)].[].[(bNumTreeaNumTree2/)].[].[(bNumTreeaNumTree1线段树※1.4线段树的简单应用线段树能解决一些最基本的统计问题。但是如果处理一些需要进行修改的动态统计问题，困难就出现了。例1在数轴上进行一系列操作。每次操作有两种类型，一种是在线段[a,b]上涂上颜色，另一种将[a,b]上的颜色擦去。问经过一系列的操作后，有多少条单位线段[k,k+1]被涂上了颜色。1线段树线段树中线段的删除只能把已经放入的线段删掉。而在这道题目中，若给线段[1,15]涂了颜色，可以把[4,9]上的颜色擦去。但线段树中只是插入了[1,15]这条线段，要删除[4,9]这条线段显然是做不到的。因此，我们有必要对线段树进行改进。1线段树※1.5线段树的改进不难想到把[1,15]这条线段删去，再插入线段[1,4]和[9,15]。但事实上并非如此简单。如下图：158811511511118若先前已插入了线段[1,8]，[8,11]。按上面的做法，只把[1,15]删去，然后插入[1,4]，[9,15]的话，[1,8]，[8,11]这两条线段并没有删去，很明显是与实际不符的。于是[1,8]，[8,11]也要修改。但若出现以下这种情况：1线段树以线段[1,15]为根的整棵线段树中的所有结点之前都已经插入过，即我们曾经这样涂过颜色：[1,2],[2,3]，……，[14,15],[1,3],[3,5],……,[13,15],[1,5]，…………，[1,15]。然后把[1,15]上的颜色擦去。那么整个线段树中的所有结点的状态就都与实际不符了，全都需要修改。修改的复杂度就是线段树的结点数。线段稍长复杂度就很高了。1线段树为了解决这个问题，我们为每个结点增加一个标记域bj。①将该线段的状态改为未被覆盖，并把该线段设为未被标记，bj=0。②把该线段的左右儿子都设为被标记，bj=-1。1、在擦去线段[a,b]之后，给它的左儿子和右儿子都做上标记，令它们的bj=-1。而不需要对整棵树进行修改。2、以后每次访问某条线段，首先检查它是否被标记，若被标记，则进行如下操作：这样做的原理很简单，以右图为例：1线段树54433221315351把线段[1,5]擦去后，给[1,3]，[3,5]加上标记。若以后我们需要用到线段[3,4]，就必须先访问[3,5]，因为[3,5]被标记，我们访问它之后标记就会传递给[3,4]和[4,5]。[3,4]就给标记上了。也就是说，标记会顺着访问[3,4]的路径一直传递下去。bj＝-1bj＝-1bj＝-1bj＝-1所以当我们需要用到下面的某条线段时，标记就会传到它那里去，使它得到更新，避免错误的发生。而对于那些以后用不到的线段，就没有更新的必要了，因此我们也不会访问到它和更新它，这样就避免了无用功的产生，提高了程序效率。bj＝01线段树进行标记更新的代码如下：ProcedureClear(Num)BeginTree[Num].Cover←0Tree[Num].bj←0Tree[Tree[Num].Left].bj←-1Tree[Tree[Num].Right].bj←-1End在访问编号为Num的线段前判断后调用1线段树引入标记域后例1就能顺利解决了，做法大体上是一样的，具体的细节可以参考论文，这里就不多说了。1线段树如果我们对整条线段[a,b]进行操作的话，我们就可以只是给[a,b]的左右儿子做上标记，而无需对以[a,b]为根的整棵子树中的所有结点进行修改。小结：1线段树※1.6线段树的推广线段树处理的是线性统计问题，而我们往往会遇到一些平面统计问题和空间统计问题，因此我们需要推广线段树，使它变成二维线段树和多维线段树。将一维线段树改成二维线段树，有两种方法。一种就是给原来线段树中的每个结点都加多一棵线段树，即“树中有树”。如下图：1线段树15133512233445151335122334451513351223344515133512233445151335122334451513351223344515133512233445[1,5][1,3][3,5][1,2][2,3][3,4][4,5]1线段树容易算出，用这种方法构造一棵矩形(x1,y1,x2,y2)的线段树的空间复杂度为。其中Long_x，Long_y分别表示矩形的长和宽。Long_y)O(Long_x相应地，时间复杂度为。其中n为操作数。(Long_y))Log(Long_x)LogO(n22由于这种线段树有两层，处理起来较麻烦。1线段树另一种方法是将线段树结点中的线段变成矩形，从而变为矩形树。因此矩形树用的是四分的思想，每个矩形分割为4个子矩形。矩形(x1,y1,x2,y2)的4个儿子如右图所示(x1,y1)(x2,y2)Son1Son2Son3Son41线段树这是一棵以矩形(1,1,4,3)为根的矩形树：(1,1)(4,3)(1,2)(2,3)(2,2)(4,3)(1,1)(2,2)(2,1)(4,2)(2,2)(3,3)(3,2)(4,3)(2,1)(3,2)(3,1)(4,2)1线段树以(x1,y1,x2,y2)为根的矩形树的空间复杂度也是。Long_y)O(Long_x由于它只有一层，处理起来比第一种方法方便。而且在这种矩形树中，标记思想依然适用。而第一种方法中，标号思想在主线段树上并不适用，只能在第二层线段树上使用。但是这种方法的时间复杂度可能会达到。比起第一种来就差了不少。Long_x)O(n1线段树对于多维的问题，第一种方法几乎不可能使用。因此我们可以仿照第二种方法。例如对于n维的问题。我们构造以(a1,a2,a3,….,an,b1,b2,b3,….,bn)为根的线段树，其中(a1,a2,a3….,an)表示的是左下角的坐标，(b1,b2,b3,….,bn)表示的是右上角的坐标。用的是2n分的思想，构造出一棵2n叉树。结点的个数变为2n×(b1-a1)×(b2-a2)×………×(bn-an)。1线段树※1.7线段树小结线段树在改进和推广之后，做到了高效地解决更多的问题。因其适用范围广和实现上的方便，线段树不失为一个优秀的方法。但线段树还是有一些缺陷的，下文将在与矩形切割进行比较的时候提及。2矩形切割矩形切割是一种处理平面上矩形的统计的方法。许多统计类的问题通过数学建模后都能转化为用矩形切割来解决。矩形切割的原型是线段切割。我们先来看看线段切割的思想。2.1线段切割例2在数轴上进行一系列操作。每次在线段[a,b]上涂色，涂的颜色可以有多种，同一线段上后涂的颜色会覆盖先涂的颜色。经过一系列操作后，对每一种颜色都求出含有该种颜色的单位线段[k,k+1]的条数。2.1线段切割由于线段之间会出现重叠，我们引入线段切割的方法对集合中的线段进行动态维护，使得所有线段两两不重叠。那么最后只需直接将同种颜色的线段长度累加，就能得出答案。若线段集合中本来有一根线段[a,b]，现在加入一根新线段[c,d]。那么它们之间的位置关系可能有以下几种：2.1线段切割dcbddccabddcdccadcbadcbadcbadcbadcbabadc⑤④③②①对于每一种位置关系，我们都可以通过切割线段[a,b]，并删除某些小段，使得它与新线段[c,d]不重叠。2.1线段切割判断线段[a,b]，[c,d]是否重叠的方法若a≥d或者c≥b，就不重叠，否则重叠。切割线段[a,b]的方法取线段[a,b]，[c,d]的交集[k1,k2]。若ak1，则加入线段[a,k1]；若k2b，则加入线段[k2,b]。删除线段[a,b]2矩形切割类似地，我们可以将矩形切割正交分解，先进行x方向上的切割，再进行y方向的切割。如右图，现在加入矩形(x3,y3,x4,y4)，对矩形(x1,y1,x2,y2)进行切割。Step1:首先从x方向上切。把线段(x1,x2)切成(x1,x3)，(x4,x2)两条线段。于是切出两个矩形——(x1,y1,x3,y2)，(x4,y1,x2,y2)。把它们加入到矩形集合中(x1,y1)(x2,y2)(x3,y3)(x4,y4)OYXx1x3x4x2Step1(x3,y3)(x4,y4)OYXx3x4Step12矩形切割Step2:接着我们再进行y方向上的切割。把线段(y1,y2)切成(y1,y3)。相应地又得到一个矩形(x3,y1,x4,y2)。把它加入到矩形集合中。y4y2y1y3(x4,y2)(x3,y1)x3x4(x3,y3)(x4,y4)OYXStep2y4y3x3x4(x3,y3)(x4,y4)OYX(x4,y2)y2Step2Step3:把原来的矩形(x1,y1,x2,y2)从矩形集合中删去。我们可以归纳出矩形切割的思想：2矩形切割1、先对被切割矩形进行x方向上的切割。取(x1,x2)，(x3,x4)的交集(k1,k2)。①若x1k1，则加入矩形(x1,y1,k1,y2)②若k2x2，则加入矩形(k2,y1,x2,y2)2、再对切剩的矩形(k1,y1,k2,y2)进行y方向上的切割。取(y1,y2)，(y3,y4)的交集(k3,k4)①若y1k3，则加入矩形(k1,y1,k2,k3)②若k4y2，则加入矩形(k1,k4,k2,y2)3、把矩形(x1,y1,x2,y2)从矩形集合中删除。2矩形切割※2.3矩形切割的推广本着矩形切割的思想，我们可以把它推广到n维。两个n维物体有重叠部分的充要条件就是它们在n个方向上都存在交集。切割的方法也是类似的：先在x方向上切，然后在y方向上切，接着在z方向上切，……，一直到在第n个方向上切。2矩形切割※2.4矩形切割的应用矩形切割可以解决几何类的统计问题。而对于其它的统计类问题，只要能建立起矩形切割的数学模型，也能用它来解决。具体例子请参考论文。3线段树与矩形切割的比较对两种方法进行比较，我们可以先从复杂度入手※3.1线段树的时空复杂度•线段树的空间复杂度是O(Long_x)。•二维线段树是O(Long_