分法与统计问题(线段树).doc

二分法与统计问题 (线段树) OICF－信息学奥林匹克综合论坛 [ 关键字 ] 线段树 二叉树 二分法 [ 摘要 ] 我们经常遇到统计的问题。这些问题的特点是，问题表现得比较简单，一般是对一定范围内的数据进行处理，用基本的方法就可以实现，但是实际处理的规模却比较大，粗劣的算法只能导致低效。为了解决这种困难，在统计中需要借助一些特殊的工具，如比较有效的数据结构来帮助解决。本文主要介绍的是分治的思想结合一定的数据结构，使得统计的过程存在一定的模式，以到达提高效率的目的。首先简要介绍线段树的基础，它是一种很适合计算几何的数据结构，同时也可以扩充到其他方面。然后将介绍 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] 不跨越区间中点，就只对左树或者右树上进行插入。否则，在左树和右树上都要进行插入。注意观察插入的路径，一条待插入区间在某一个结点上进行“跨越”，此后两条子树上都要向下插入，但是这种跨越不可能多次发生。插入区间的时间复杂度是