资源描述：
《算法合集之《二分法与统计问题》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、本资料由-大学生创业
2、创业
3、创业网http://www.chuangyw.com/提供资料二分法与统计问题淮阴中学李睿[关键字]线段树二叉树二分法[摘要]我们经常遇到统计的问题。这些问题的特点是，问题表现得比较简单，一般是对一定范围内的数据进行处理，用基本的方法就可以实现，但是实际处理的规模却比较大，粗劣的算法只能导致低效。为了解决这种困难，在统计中需要借助一些特殊的工具，如比较有效的数据结构来帮助解决。本文主要介绍的是分治的思想结合一定的数据结构，使得统计的过程存在一定的模式，以到达提高效率的目的。首先简要介绍线段树的
4、基础，它是一种很适合计算几何的数据结构，同时也可以扩充到其他方面。然后将介绍IOI2001中涉及的一种特殊的统计方法。接着将会介绍一种与线段树有所不同的构造模式，它的形式是二叉排序树，将会发现这种方法是十分灵活的，进一步，我们将略去对它的构造，在有序表中进行虚实现。目录一线段树1.1线段树的构造思想1.2线段树处理数据的基本方法1.3应用的优势1.4转化为对点的操作二一种解决动态统计的静态方法2.1问题的提出2.2数据结构的构造和设想2.3此种数据结构的维护2.4应用的分析三在二叉排序树上实现统计3.1构造可用于统计的静
5、态二叉排序树3.2进行统计的方法分析3.3一个较复杂的例子四虚二叉树4.1虚二叉树实现的形态4.2一个具体的例子4.3最长单调序列的动态规划优化问题在线代理
6、网页代理
7、代理网页
8、http://www.dailiav.com减肥药排行榜
9、淘宝最好的减肥药
10、什么减肥药效果最好
11、减肥瘦身药
12、http://pigproxy.cn本资料由-大学生创业
13、创业
14、创业网http://www.chuangyw.com/提供资料[正文]一线段树在一类问题中，我们需要经常处理可以映射在一个坐标轴上的一些固定线段，例如说映射在OX轴上的线段。由
15、于线段是可以互相覆盖的，有时需要动态地取线段的并，例如取得并区间的总长度，或者并区间的个数等等。一个线段是对应于一个区间的，因此线段树也可以叫做区间树。1.1线段树的构造思想线段树处理的是一定的固定线段，或者说这些线段是可以对应于有限个固定端点的。处理问题的时候，首先抽象出区间的端点，例如说N个端点ti(1≤i≤N)。那么对于任何一个要处理的线段（区间）[a,b]来说，总可以找到相应的i,j，使得ti=a,tj=b,1≤i≤j≤N。这样的转换就使得线段树上的区间表示为整数，通过映射转换，可以使得原问题实数区间得到同样的处
16、理。下图显示了一个能够表示[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),直到分裂为一个初等区间为止。线段树的平分构造，实际上是用了二分的方法。线段树是平衡树，它的深度为lg(b-a)。如果采用动态的数据结构来实现线段树，结点的构造可以用如下数据结构：TypeTnode=^Tre
17、enode;Treenode=recordB,E:integer;Count:integer;LeftChild,Rightchild:Tnode;End;其中B和E表示了该区间为[B,E]；Count在线代理
18、网页代理
19、代理网页
20、http://www.dailiav.com减肥药排行榜
21、淘宝最好的减肥药
22、什么减肥药效果最好
23、减肥瘦身药
24、http://pigproxy.cn本资料由-大学生创业
25、创业
26、创业网http://www.chuangyw.com/提供资料为一个计数器，通常记录覆盖到此区间的线段的个数。LeftCh
27、ild和RightChild分别是左右子树的根。或者为了方便，我们也采用静态的数据结构。用数组B[]，E[]，C[]，LSON[]，RSON[]。设一棵线段树的根为v。那么B[v],E[v]就是它所表示区间的界。C[v]仍然用来作计数器。LSON[v]，RSON[v]分别表示了它的左儿子和右儿子的根编号。注意，这只是线段树的基本结构。通常利用线段树的时候需要在每个结点上增加一些特殊的数据域，并且它们是随线段的插入删除进行动态维护的。这因题而异，同时又往往是解题的灵魂。1.2线段树处理数据的基本方法线段树的最基本的建立，插
28、入和删除的过程，以静态数据结构为例。建立线段树（a,b）:设一个全局变量n，来记录一共用到了多少结点。开始n=0procedureBUILD(a,b)beginn←n+1v←nB[v]←aE[v]←bC[v]←0ifb–a>1thenbeginLSON[v]←n+1BUILD(a,)RSON[v]←n+1BUILD(
