1、解决动态统计问题的两把利刃 剖析线段树与矩形切割广东北江中学 薛矛目录 1 线段树 2 矩形切割 3 线段树与矩形切割的比较 4 总结 1.1 线段树的结构 1 线段树 1.2 线段树的建立Procedure MakeTree(a,b)Var Now:LongintBegintot tot + 1 Now totTreeNow.a a TreeNow.b bIf a +1 then Insert(TreeNum.Right)End1 线段树删除一条线段 c,dProcedure Delete(Num)BeginIf (c thenDelete(TreeNum.Right)End1 线段树 1.
2、4 线段树的简单应用线段树能解决一些最基本的统计问题。但是如果处理一些需要进行修改的动态统计问题，困难就出现了。例 1 在数轴上进行一系列操作。每次操作有两种类型，一种是在线段 a,b上涂上颜色，另一种将 a,b上的颜色擦去。问经过一系列的操作后，有多少条单位线段k,k+1被涂上了颜色。1 线段树线段树中线段的删除只能把已经放入的线段删掉 。而在这道题目中，若给线段 1,15涂了颜色，可以把 4,9上的颜色擦去。但线段树中只是插入了 1,15这条线段，要删除 4,9这条线段显然是做不到的。因此，我们有必要对线段树进行改进。 1 线段树 1.5 线段树的改进不难想到把 1,15这条线段删去，再插
3、入线段 1,4和 9,15。但事实上并非如此简单。 如下图：若先前已插入了线段 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、以后每次访问某条线段，首先检查它是否被标记，若被标记，则进行如下操作：
