看到一篇比较好的论文 转给大家看其中的线段树部分
二分法与统计问题
淮阴中学
李睿
[
关键字
]
线段树
二叉树
二分法
[
摘要
]
我们经常遇到统计的问题。这些问题的特点是,问题表现得比较简单,一般是对一定范围内的数据进行处理,用基本的方法就可以实现,但是实际处理的规模却比较大,粗劣的算法只能导致低效。为了解决这种困难,在统计中需要借助一些特殊的工具,如比较有效的数据结构来帮助解决。本文主要介绍的是分治的思想结合一定的数据结构,使得统计的过程存在一定的模式,以到达提高效率的目的。首先简要介绍线段树的基础,它是一种很适合计算几何的数据结构,同时也可以扩充到其他方面。然后将介绍
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-a>1
,设根为
[a,b]
的线段树为
T(a,b),
则进一步将此线段树分为左子树
T(a,(a+b)/2),
以及右子树
T((a+b)/2,b),
直到分裂为一个初等区间为止。
线段树的平分构造,实际上是用了二分的方法。线段树是平衡树,它的深度为
lg(b-a)
。
如果采用动态的数据结构来实现线段树,结点的构造可以用如下数据结构:
Type
Tnode=^Treenode;
Treenode=record
B,E:integer;
Count:integer;
LeftChild,Rightchild:Tnode;
End;
|
其中
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
procedure
BUILD(a,b)
begin
n
←
n+1//n
记录一共用到了多少结点
v
←
n
B[v]
←
a
E[v]
←
b
C[v]
←
0
if
b – a>1 then
begin
LSON[v]
←
n+1 //
节点编号
BUILD(a,) //
注意
N
在这里变化了
RSON[v]
←
n+1//
节点编号
BUILD( ,b)
end
end
|
将区间
[c,d]
插入线段树
T(a,b),
并设
T(a,b)
的根编号为
v
:
procedure
INSERT(c,d;v)
begin
if c≤B[v] and E[v]
≤
d then C[v]
←
C[v]+1
else if
c< then INSERT(c,d;LSON[v]);
if
d> then INSERT(c,d;RSON[v]);
end//
如果跨区间了
我们将看到两次插入
|
对于此算法的解释:如果
[c
,
d]
完全覆盖了当前线段,那么显然该结点上的基数(即覆盖线段数)加
1
。否则,如果
[c
,
d]
不跨越区间中点,就只对左树或者右树上进行插入。否则,在左树和右树上都要进行插入。注意观察插入的路径,一条待插入区间在某一个结点上进行“跨越”,此后两条子树上都要向下插入,但是这种跨越不可能多次发生。插入区间的时间复杂度是
O(logn)
。
在线段上树删除一个区间与插入的方法几乎是完全类似的:
将区间
[c,d]
删除于线段树
T(a,b),
并设
T(a,b)
的根编号为
v
:
procedure
DELETE(c,d;v)
begin
if c≤B[v] and E[v]
≤
d then C[v]
←
C[v]-1
else if
c< then DELETE(c,d;LSON[v]);
if
d> then DELETE(c,d;RSON[v]);
end
|
特别注意
:只有曾经插入过的区间才能够进行删除。这样才能保证线段树的维护是正确的。例如,在先前所示的线段树上不能插入区间
[1
,
10]
,然后删除区间
[2
,
3]
,这显然是不能得到正确结果的。
线段树的作用主要体现在可以动态维护一些特征,例如说要得到线段树上线段并集的长度,增加一个数据域
M[v]
,讨论:
如果
C[v]>0,M[v] = E[v]-B[v]; //yes
C[v]=0
且
v
是叶子结点,
M[v]=0
;
C[v]=0
且
v
是内部结点,
M[v]=M[LSON[v]]+M[RSON[v]];
只要每次插入或删除线段区间时,在访问到的结点上更新
M
的值,不妨称之为
UPDATA
,就可以在插入和删除的同时维持好
M
。求整个线段树的并集长度时,只要访问
M[ ROOT]
的值。这在许多动态维护的题目中是非常有用的,它使得每次操作的维护费用只有
logn
。
类似的,还有求并区间的个数等等。这里不再深入列举。
1.3
应用的优势
线段树的构造主要是对区间线段的处理,它往往被应用于几何计算问题中。比如说处理一组矩形问题时,可以用来求矩形并图后的轮廓周长和面积等等,比普通的离散化效率更高。这些应用可以在相关资料中查到。这里不作深入。
1.4
转化为对点的操作
线段树处理的是区间线段的问题,有些统计问题处理的往往是点的问题。而点也是可以理解为特殊的区间的。这时往往将线段树的构造进行变形,也就是说可以转化为记录点的结构。
变形:
将线段树上的初等区间分裂为具体的点,用来计数。即不存在
(a,a+1)
这样的区间,每个点分裂为
a
和
a+1
。同时按照区间的中点分界时,点要么落在左子树上,要么落在右子树上。如下图:
原线段数记录基数的
C[v]
这时就可以用来计算落在定区间内的点个数了。原搜索路径也发生了改变,不存在“跨越”的情况。同时插入每个点的时候都必须深入到叶结点,因此一般来说都要有
logn
的复杂度。
应用这样的线段树一方面是方便计数。另一方面由于它实际上是排序二叉树,所以容易找出最大和最小来。下面就看一个找最大最小的例子。
[
例一
]PROMOTION
问题(
POI0015
)
问题大意:
一位顾客要进行
n
(
1
≤
n
≤
5000
)天的购物,每天他会有一些帐单。每天购物以后,他从以前的所有帐单中挑出两张帐单,分别是面额最大的和面额最小的一张,并把这两张帐单从记录中去掉。剩下的帐单留在以后继续统计。输入的数据保证,所有
n
天的帐单总数不超过
1000000
,并且每份帐单的面额值是
1
到
1000000
之间的整数。保证每天总可以找到两张帐单。
解决方法:
本题明显地体现了动态维护的特性,即每天都要插入一些面额随机的帐单,同时还要找出最大和最小的两张。不妨建立前面所说的线段树,这棵线段树的范围是
[1
,
1000000]
,即我们把所有面额的帐单设为一个点。插入和删除一份帐单是显然的。如何找到最大的帐单呢?显然,对于一个树
v
来说,如果
C[LSON[v]]>0,
那么树
v
中的最小值一定在它的左子树上。同样,如果
C[RSON[v]]>0
,它的最大值在右子树上;否则,如果
C[LSON[v]]=0
,那么最大最小的两份帐单都在右子树上。所以线段树的计数其实为我们提供了线索。显然对于一个特定面额来说。它的插入,删除,查找路径是相同的,长度为树的深度,即
log1000000=20
。如果总共有
N
张帐单,那么考虑极限时的复杂度为
N*20+n*20*2
。这比普通排序的实现要简单得多。普通排序是
(N*n*20);
本题还可以采取巧妙的办法,线段树不一定要存帐单的具体面额。由于我们对
1000000
种面额都进行了保存,所以线段树显得比较庞大。采取一种方法:我们用
hash
来保存每一种面额的帐单数目,然后对于一个具体的帐单,例如面额为
V
,我们在线段树中保存
V/100
的值,也就是说,我们把连续的
100
种面额的帐单看成是一组。由于
V
的范围是
[1..1000000]
,所以线段树中有
10000
个点。在找最大的数的时候,首先找到最小的组,然后在
hash
里对这个组进行搜索,显然这个搜索的规模不会超过
100
。由于线段树变小了,所以树的深度只有
14
左右,整个问题的复杂度极限为
N*14+n*14*100*2
,对于问题的规模来说,仍然是高效率的。但这样做比前种方法在一定程度上节省了空间。同时实际上也提醒了我们对线段树应该加以灵活的应用。