二分法及统计问题(线段树)

《二分法及统计问题(线段树)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、二分法与统计问题(线段树)OICF－信息学奥林匹克综合论坛[关键字]线段树二叉树二分法[摘要]我们经常遇到统计的问题。这些问题的特点是，问题表现得比较简单，一般是对一定范围内的数据进行处理，用基本的方法就可以实现，但是实际处理的规模却比较大，粗劣的算法只能导致低效。为了解决这种困难，在统计中需要借助一些特殊的工具，如比较有效的数据结构来帮助解决。本文主要介绍的是分治的思想结合一定的数据结构，使得统计的过程存在一定的模式，以到达提高效率的目的。首先简要介绍线段树的基础，它是一种很适合计算几何的数据结构，同时也可以扩充到其他方面。然后将

2、介绍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虚二叉树实

3、现的形态4.2一个具体的例子4.3最长单调序列的动态规划优化问题[正文]一线段树在一类问题中，我们需要经常处理可以映射在一个坐标轴上的一些固定线段，例如说映射在OX轴上的线段。由于线段是可以互相覆盖的，有时需要动态地取线段的并，例如取得并区间的总长度，或者并区间的个数等等。一个线段是对应于一个区间的，因此线段树也可以叫做区间树。1.1线段树的构造思想线段树处理的是一定的固定线段，或者说这些线段是可以对应于有限个固定端点的。处理问题的时候，首先抽象出区间的端点，例如说N个端点ti(1≤i≤N)。那么对于任何一个要处理的线段（区间）[a

4、,b]来说，总可以找到相应的i,j，使得ti=a,tj=b,1≤i≤j≤N。这样的转换就使得线段树上的区间表示为整数，通过映射转换，可以使得原问题实数区间得到同样的处理。下图显示了一个能够表示[1，10]的线段树：线段树是一棵二叉树，树中的每一个结点表示了一个区间[a,b]。每一个叶子节点上a+1=b,这表示了一个初等区间。对于每一个内部结点b-a>1，设根为[a,b]的线段树为T(a,b),则进一步将此线段树分为左子树T(a,(a+b)/2),以及右子树T((a+b)/2,b),直到分裂为一个初等区间为止。线段树的平分构造，实际上

5、是用了二分的方法。线段树是平衡树，它的深度为lg(b-a)。如果采用动态的数据结构来实现线段树，结点的构造可以用如下数据结构：TypeTnode=^Treenode;Treenode=recordB,E:integer;Count:integer;LeftChild,Rightchild:Tnode;End;其中B和E表示了该区间为[B,E]；Count为一个计数器，通常记录覆盖到此区间的线段的个数。LeftChild和RightChild分别是左右子树的根。或者为了方便，我们也采用静态的数据结构。用数组B[]，E[]，C[]，LS

6、ON[]，RSON[]。设一棵线段树的根为v。那么B[v],E[v]就是它所表示区间的界。C[v]仍然用来作计数器。LSON[v]，RSON[v]分别表示了它的左儿子和右儿子的根编号。注意，这只是线段树的基本结构。通常利用线段树的时候需要在每个结点上增加一些特殊的数据域，并且它们是随线段的插入删除进行动态维护的。这因题而异，同时又往往是解题的灵魂。1.2线段树处理数据的基本方法线段树的最基本的建立，插入和删除的过程，以静态数据结构为例。建立线段树（a,b）:设一个全局变量n，来记录一共用到了多少结点。开始n=0procedureBU

7、ILD(a,b)beginn←n+1//n记录一共用到了多少结点v←nB[v]←aE[v]←bC[v]←0ifb–a>1thenbeginLSON[v]←n+1//节点编号BUILD(a,)//注意N在这里变化了RSON[v]←n+1//节点编号BUILD(,b)endend将区间[c,d]插入线段树T(a,b),并设T(a,b)的根编号为v：procedureINSERT(c,d;v)beginifc≤B[v]andE[v]≤dthenC[v]←C[v]+1elseifct

8、henINSERT(c,d;RSON[v]);end//如果跨区间了我们将看到两次插入对于此算法的解释：如果[c，d]完全覆盖了当前线段，那么显然该结点上的基数（即覆盖线段数）加1。否则，如果[c，d]不跨越区间中点，就只对左树或者右