A-A+

《挑战程序设计竞赛》读书笔记(六)线段树和RMQ

2014年08月04日 算法 暂无评论 阅读 993 次
摘要:

本文是《挑战程序设计竞赛》中线段树一节的读书笔记。主要介绍了线段树和RMQ(range minimun query)的原理和实现。

线段树:

线段树适合于处理区间。如图组织管理区间。

rmq

节点可以存放不同的数据,在书中实现了RMQ(Range Minimum Query)操作的数据结构。

RMQ是指给定若干个数据a[],找出a[i…j]的最小值,同时允许更新a[k]。

 

针对RMQ,线段树的每个节点维护对应区间的最小值。如图所示。

min

那如何执行RMQ呢,我们以求a[0..6]的最小值为例说明。为方便,我们对所有节点进行编号,按行从0开始,如图。现在,考察a[0..6]的最小值。

get_range_min

首先,我们根据图能够知道,第0个节点存放了a[0..7]的最小值,所以,我们只能继续递归处理节点1和节点2。节点1表示了a[0..3]的最小值3,这个最小值对我们来说是有用的,并且我们也没必要继续考察节点3和节点4了。然后考察节点2,同节点0,我们再递归,如此继续,我们发现,为了求a[0..6]的最小值,我们只需比较图中橙黄色的三个数字就可以了。

所以,根据当前节点对应区间和所查询的区间的关系,分成如下三种情况。

1.  如果当前节点对应区间和所查询的区间没有交集,那么说明这个区间不影响我们查找最小值,所以当前节点返回一个不影响结果的值。

2.  如果所查询的区间包含了当前节点对应的区间,那么就返回当前节点的值作为候选最小值之一。

3.  不是上述两种情况(如同本例中节点0的情况),需要递归求解。

 

这个算法的复杂度是多少呢?虽然看起来像是二叉树递归,但是,复杂度是O(n),因为节点个数总共是2n个。

 

下面我们看如何更新一个值,即设置a[k]=value。我们以更新a[0]=2为例。

由于父子节点之间是包含关系,所以更新a[k]只需要从下往上,一直更新到根节点即可。

例如,更新a[0]=2,则为:

从节点7更新节点3,然后是节点1,最后是节点0,如果需要更新最小值,就更新,否则保持不变停止(没必要继续向上更新了)。

update

关于RMQ的实现代码,我写了一份,供大家参考。

 

给我留言