oyjpArt ACM/ICPC算法程序设计空间

// I am new in programming, welcome to my blog
I am oyjpart(alpc12, 四城)
posts - 224, comments - 694, trackbacks - 0, articles - 6

[转]线段树

Posted on 2006-11-24 20:19 oyjpart 阅读(6022) 评论(0)  编辑 收藏 引用 所属分类: ACM/ICPC或其他比赛

看到一篇比较好的论文 转给大家看其中的线段树部分
二分法与统计问题

淮阴中学 李睿

[ 关键字 ]

       线段树 二叉树 二分法

 

[ 摘要 ]

       我们经常遇到统计的问题。这些问题的特点是,问题表现得比较简单,一般是对一定范围内的数据进行处理,用基本的方法就可以实现,但是实际处理的规模却比较大,粗劣的算法只能导致低效。为了解决这种困难,在统计中需要借助一些特殊的工具,如比较有效的数据结构来帮助解决。本文主要介绍的是分治的思想结合一定的数据结构,使得统计的过程存在一定的模式,以到达提高效率的目的。首先简要介绍线段树的基础,它是一种很适合计算几何的数据结构,同时也可以扩充到其他方面。然后将介绍 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 ,对于问题的规模来说,仍然是高效率的。但这样做比前种方法在一定程度上节省了空间。同时实际上也提醒了我们对线段树应该加以灵活的应用。


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理