算法合集之《分法与统计问题》.docVIP

二分法与统计问题 淮阴中学 李睿 [关键字] 线段树 二叉树 二分法 [摘要] 我们经常遇到统计的问题。这些问题的特点是，问题表现得比较简单，一般是对一定范围内的数据进行处理，用基本的方法就可以实现，但是实际处理的规模却比较大，粗劣的算法只能导致低效。为了解决这种困难，在统计中需要借助一些特殊的工具，如比较有效的数据结构来帮助解决。本文主要介绍的是分治的思想结合一定的数据结构，使得统计的过程存在一定的模式，以到达提高效率的目的。首先简要介绍线段树的基础，它是一种很适合计算几何的数据结构，同时也可以扩充到其他方面。然后将介绍IOI2001中涉及的一种特殊的统计方法。接着将会介绍一种与线段树有所不同的构造模式，它的形式是二叉排序树，将会发现这种方法是十分灵活的，进一步，我们将略去对它的构造，在有序表中进行虚实现。 目录 一 线段树 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 最长单调序列的动态规划优化问题 [正文] 一 线段树 在一类问题中，我们需要经常处理可以映射在一个坐标轴上的一些固定线段，例如说映射在OX轴上的线段。由于线段是可以互相覆盖的，有时需要动态地取线段的并，例如取得并区间的总长度，或者并区间的个数等等。一个线段是对应于一个区间的，因此线段树也可以叫做区间树。 1.1线段树的构造思想 线段树处理的是一定的固定线段，或者说这些线段是可以对应于有限个固定端点的。处理问题的时候，首先抽象出区间的端点，例如说N个端点ti(1≤i≤N)。那么对于任何一个要处理的线段（区间）[a,b]来说，总可以找到相应的i,j，使得ti=a,tj=b,1≤i≤j≤N。这样的转换就使得线段树上的区间表示为整数，通过映射转换，可以使得原问题实数区间得到同样的处理。下图显示了一个能够表示[1，10]的线段树： 线段树是一棵二叉树，树中的每一个结点表示了一个区间[a,b]。每一个叶子节点上a+1=b,这表示了一个初等区间。对于每一个内部结点b-a1，设根为[a,b]的线段树为T(a,b),则进一步将此线段树分为左子树T(a,(a+b)/2),以及右子树T((a+b)/2,b),直到分裂为一个初等区间为止。 线段树的平分构造，实际上是用了二分的方法。线段树是平衡树，它的深度为lg(b-a)。 如果采用动态的数据结构来实现线段树，结点的构造可以用如下数据结构： 其中B和E表示了该区间为[B,E]；Count为一个计数器，通常记录覆盖到此区间的线段的个数。LeftChild和RightChild分别是左右子树的根。 或者为了方便，我们也采用静态的数据结构。用数组B[]，E[]，C[]，LSON[]，RSON[]。设一棵线段树的根为v。那么B[v],E[v]就是它所表示区间的界。C[v]仍然用来作计数器。LSON[v]，RSON[v]分别表示了它的左儿子和右儿子的根编号。 注意，这只是线段树的基本结构。通常利用线段树的时候需要在每个结点上增加一些特殊的数据域，并且它们是随线段的插入删除进行动态维护的。这因题而异，同时又往往是解题的灵魂。 1.2 线段树处理数据的基本方法 线段树的最基本的建立，插入和删除的过程，以静态数据结构为例。 建立线段树（a,b）: 设一个全局变量n，来记录一共用到了多少结点。开始n=0 将区间[c,d]插入线段树T(a,b),并设T(a,b)的根编号为v： 对于此算法的解释：如果[c，d]完全覆盖了当前线段，那么显然该结点上的基数（即覆盖线段数）加1。否则，如果[c，d]不跨越区间中点，就只对左树或者右树上进行插入。否则，在左树和右树上都要进行插入。注意观察插入的路径，一条待插入区间在某一个结点上进行“跨越”，此后两条子树上都要向下插入，但是这种跨越不可能多次发生。插入区间的时间复杂度是O(logn)。 在线段上树删除一个区间与插入的方法几乎是完全类似的： 将区间[c,d]删除于线段树T(a,b),并设T(a,b)的根编号为v： 特别注意：只有曾经插入过的区间才能够进行删除。这样才能保证线段树的维护是正确的。例如，在先前所示的线段树上不能插入区间[1，10]，然后删除区间[2，3]，这显然是不能得到正确结果的。 线段树的作用主要体现在可以动态维护一些特征，例如说要得到线段树上线段并集的长度，增加一个数据域 M[v]，讨论：