《23%-数据结构与算法-排序算法-《二分法与统计问题》》由会员分享，可在线阅读，更多相关《23%-数据结构与算法-排序算法-《二分法与统计问题》（22页珍藏版）》请在金锄头文库上搜索。
1、二分法与统计问题 江苏淮阴中学 李睿- 1 -二分法与统计问题淮阴中学 李睿关键字线段树 二叉树 二分法 摘要我们经常遇到统计的问题。这些问题的特点是，问题表现得比较简单，一般是对一定范围内的数据进行处理，用基本的方法就可以实现，但是实际处理的规模却比较大，粗劣的算法只能导致低效。为了解决这种困难，在统计中需要借助一些特殊的工具，如比较有效的数据结构来帮助解决。本文主要介绍的是分治的思想结合一定的数据结构，使得统计的过程存在一定的模式，以到达提高效率的目的。首先简要介绍线段树的基础，它是一种很适合计算几何的数据结构，同时也可以扩充到其他方面。然后将介绍 IOI2001 中涉及的一种特殊的统计方
2、法。接着将会介绍一种与线段树有所不同的构造模式，它的形式是二叉排序树，将会发现这种方法是十分灵活的，进一步，我们将略去对它的构造，在有序表中进行虚实现。目录一 线段树1.1 线段树的构造思想1.2 线段树处理数据的基本方法1.3 应用的优势1.4 转化为对点的操作二 一种解决动态统计的静态方法2.1 问题的提出2.2 数据结构的构造和设想2.3 此种数据结构的维护2.4 应用的分析三 在二叉排序树上实现统计3.1 构造可用于统计的静态二叉排序树3.2 进行统计的方法分析3.3 一个较复杂的例子四 虚二叉树4.1 虚二叉树实现的形态4.2 一个具体的例子4.3 最长单调序列的动态规划优化问题二分
3、法与统计问题 江苏淮阴中学 李睿- 2 -正文一 线段树在一类问题中，我们需要经常处理可以映射在一个坐标轴上的一些固定线段，例如说映射在 OX 轴上的线段。由于线段是可以互相覆盖的，有时需要动态地取线段的并，例如取得并区间的总长度，或者并区间的个数等等。一个线段是对应于一个区间的，因此线段树也可以叫做区间树。1.1 线段树的构造思想线段树处理的是一定的固定线段，或者说这些线段是可以对应于有限个固定端点的。处理问题的时候，首先抽象出区间的端点，例如说 N 个端点ti(1iN)。那么对于任何一个要处理的线段（区间）a,b来说，总可以找到相应的 i,j，使得 ti=a,tj=b,1 ijN。这样的转
4、换就使得线段树上的区间表示为整数，通过映射转换，可以使得原问题实数区间得到同样的处理。下图显示了一个能够表示1，10 的线段树：1,10 1,5 5,10 1,3 3,5 5,7 7,10 1,2 2,3 3,4 4,5 5,6 6,7 7,8 8,10 8,9 9,10 线段树是一棵二叉树，树中的每一个结点表示了一个区间a,b。每一个叶子节点上 a+1=b,这表示了一个初等区间。对于每一个内部结点 b-a1，设根为a,b的线段树为 T(a,b),则进一步将此线段树分为左子树 T(a,(a+b)/2),以及右子树T(a+b)/2,b),直到分裂为一个初等区间为止。线段树的平分构造，实际上是用了
5、二分的方法。线段树是平衡树，它的深度为 lg(b-a)。如果采用动态的数据结构来实现线段树，结点的构造可以用如下数据结构：其中 B 和 E 表示了该区间为B,E；Count 为一个计数器，通常记录覆盖到TypeTnode=Treenode;Treenode=recordB,E:integer; Count:integer;LeftChild,Rightchild:Tnode;End;二分法与统计问题 江苏淮阴中学 李睿- 3 -此区间的线段的个数。LeftChild 和 RightChild 分别是左右子树的根。或者为了方便，我们也采用静态的数据结构。用数组 B，E，C，LSON，RSON。设
6、一棵线段树的根为 v。那么 Bv,Ev就是它所表示区间的界。Cv 仍然用来作计数器。LSONv，RSONv分别表示了它的左儿子和右儿子的根编号。注意，这只是线段树的基本结构。通常利用线段树的时候需要在每个结点上增加一些特殊的数据域，并且它们是随线段的插入删除进行动态维护的。这因题而异，同时又往往是解题的灵魂。1.2 线段树处理数据的基本方法线段树的最基本的建立，插入和删除的过程，以静态数据结构为例。建立线段树（a,b ）:设一个全局变量 n，来记录一共用到了多少结点。开始 n=0将区间c,d插入线段树 T(a,b),并设 T(a,b)的根编号为 v：procedure BUILD(a,b)be
7、ginn n+1v nBvaEvbCv0if b a1 thenbeginLSONvn+1BUILD(a, )2/(baRSONvn+1BUILD( ,b)/)(endendprocedure INSERT(c,d;v)beginif cBv and Evd then Cv Cv+1else if c then INSERT(c,d;RSONv);end二分法与统计问题 江苏淮阴中学 李睿- 4 -对于此算法的解释：如果c，d 完全覆盖了当前线段，那么显然该结点上的基数（即覆盖线段数）加 1。否则，如果c，d 不跨越区间中点，就只对左树或者右树上进行插入。否则，在左树和右树上都要进行插入。注意
8、观察插入的路径，一条待插入区间在某一个结点上进行“跨越” ，此后两条子树上都要向下插入，但是这种跨越不可能多次发生。插入区间的时间复杂度是 O(logn)。在线段上树删除一个区间与插入的方法几乎是完全类似的：将区间c,d删除于线段树 T(a,b),并设 T(a,b)的根编号为 v：特别注意：只有曾经插入过的区间才能够进行删除。这样才能保证线段树的维护是正确的。例如，在先前所示的线段树上不能插入区间1，10，然后删除区间2 ，3，这显然是不能得到正确结果的。线段树的作用主要体现在可以动态维护一些特征，例如说要得到线段树上线段并集的长度，增加一个数据域 Mv，讨论：如果 Cv0,Mv = Ev-B
9、v;Cv=0 且 v 是叶子结点，Mv=0；Cv=0 且 v 是内部结点，Mv=MLSONv+MRSONv;只要每次插入或删除线段区间时，在访问到的结点上更新 M 的值，不妨称之为 UPDATA，就可以在插入和删除的同时维持好 M。求整个线段树的并集长度时，只要访问 M ROOT的值。这在许多动态维护的题目中是非常有用的，它使得每次操作的维护费用只有 logn。类似的，还有求并区间的个数等等。这里不再深入列举。1.3 应用的优势线段树的构造主要是对区间线段的处理，它往往被应用于几何计算问题中。比如说处理一组矩形问题时，可以用来求矩形并图后的轮廓周长和面积等等，比普通的离散化效率更高。这些应用可
10、以在相关资料中查到。这里不作深入。1.4 转化为对点的操作procedure DELETE(c,d;v)beginif cBv and Evd then Cv Cv-1else if c then DELETE(c,d;RSONv);end二分法与统计问题 江苏淮阴中学 李睿- 5 -线段树处理的是区间线段的问题，有些统计问题处理的往往是点的问题。而点也是可以理解为特殊的区间的。这时往往将线段树的构造进行变形，也就是说可以转化为记录点的结构。变形：将线段树上的初等区间分裂为具体的点，用来计数。即不存在(a,a+1)这样的区间，每个点分裂为 a 和 a+1。同时按照区间的中点分界时，点要么落在左
11、子树上，要么落在右子树上。如下图：1,10 1,4 5,10 1,2 3,4 5,7 8,10 1 2 3 4 5， 6 7 8,9 10 8 5 6 9 原线段数记录基数的 Cv这时就可以用来计算落在定区间内的点个数了。原搜索路径也发生了改变，不存在“跨越”的情况。同时插入每个点的时候都必须深入到叶结点，因此一般来说都要有 logn 的复杂度。应用这样的线段树一方面是方便计数。另一方面由于它实际上是排序二叉树，所以容易找出最大和最小来。下面就看一个找最大最小的例子。例一PROMOTION 问题（POI0015）问题大意：一位顾客要进行 n（1n5000）天的购物，每天他会有一些帐单。每天购物
12、以后，他从以前的所有帐单中挑出两张帐单，分别是面额最大的和面额最小的一张，并把这两张帐单从记录中去掉。剩下的帐单留在以后继续统计。输入的数据保证，所有 n 天的帐单总数不超过 1000000，并且每份帐单的面额值是1 到 1000000 之间的整数。保证每天总可以找到两张帐单。解决方法：本题明显地体现了动态维护的特性，即每天都要插入一些面额随机的帐单，同时还要找出最大和最小的两张。不妨建立前面所说的线段树，这棵线段树的范围是1 ，1000000，即我们把所有面额的帐单设为一个点。插入和删除一份帐单是显然的。如何找到最大的帐单呢？显然，对于一个树 v 来说，如果CLSONv0,那么树 v 中的最
13、小值一定在它的左子树上。同样，如果CRSONv0，它的最大值在右子树上；否则，如果 CLSONv=0，那么最大最小的两份帐单都在右子树上。所以线段树的计数其实为我们提供了线索。显然对于一个特定面额来说。它的插入，删除，查找路径是相同的，长度为树的深度，即 log1000000=20。如果总共有 N 张帐单，那么考虑极限时的复杂度为 N*20+n*20*2。这比普通排序的实现要简单得多。本题还可以采取巧妙的办法，线段树不一定要存帐单的具体面额。由于我们对 1000000 种面额都进行了保存，所以线段树显得比较庞大。采取一种方法：我们用 hash 来保存每一种面额的帐单数目，然后对于一个具体的帐单
14、，例如面二分法与统计问题 江苏淮阴中学 李睿- 6 -额为 V，我们在线段树中保存 V/100 的值，也就是说，我们把连续的 100 种面额的帐单看成是一组。由于 V 的范围是1.1000000，所以线段树中有 10000 个点。在找最大的数的时候，首先找到最小的组，然后在 hash 里对这个组进行搜索，显然这个搜索的规模不会超过 100。由于线段树变小了，所以树的深度只有 14 左右，整个问题的复杂度极限为 N*14+n*14*100*2，对于问题的规模来说，仍然是高效率的。但这样做比前种方法在一定程度上节省了空间。同时实际上也提醒了我们对线段树应该加以灵活的应用。二 一种解决动态统计的静态
15、方法2.1 问题的提出例二 IOI2001 MOBILES正如在摘要中所说的，这类题目的意思非常简单明了，而且用几个小循环就可以解决。但是面对可能将要处理的规模，我们却望而却步了，因为简单的实现效率实在太低了。本题的一种完美解决方法用到了一种特殊的结构定义。问题是二维的，注意到降格的思想，我们对一维的问题进行讨论，然后只要稍微进行推广。一维的序列求和问题是这样的 ：设序列的元素存储在 a中，a 的下标是 1.n的正整数，需要动态地更新某个 ax的值，同时要求出 ax1到 ay1这一段所有元素的和。这个问题与 MOBILES 问题实际上提法是一样的。2.2 数据结构的构造和设想本题利用前面讲的线段树实际上就可以得到高效地解决。因为我们知道计算 ax1
