LCA RMQ 最小公共祖先 区间最小值

翻译

 

【原文见http://www.topcoder.com/tc?

module=Static&d1=tutorials&d2=lowestCommonAncestor】

作者：







A <O(N), O(sqrt(N))> solution

Sparse Table (ST) algorithm

Segment Trees

Lowest Common Ancestor (LCA)

A <O(N), O(sqrt(N))> solution

Another easy solution in <O(N logN, O(logN)>

Reduction from LCA to RMQ

From RMQ to LCA

An <O(N), O(1)> algorithm for the restricted RMQ

Conclusion

询可以在常数时间内得到答案。他们的工作已经得到了广泛的延伸，这篇教程将展示一些有趣的方法，而

它们还也可以用在其他的问题上。

 让我们考虑一个不太抽象的 LCA 的例子：生命树。地球上当前的居住者是由其他物种进化而来已经

是一个不争的事实。这种进化结构可以表示成一棵树，其中节点表示物种，而它的孩子结点表示从该物种

直接进化得到的物种。现在通过在树中查找一些结点的 LCA 把具有相似特征的物种划分成组，我们可以

找出两个物种共同的祖先，并且我们可以知道它们所拥有的相似特征是来自于那个祖先。

 Range Minimum Query(RMQ)被用在数组中用来查找两个指定索引中具有最小值的元素的位置。

我们后面将会看到 LCA 问题可以归约成一个带限制的 RMQ 问题，其中相邻的数组元素相差 1。

 尽管如此, RMQ 并不是仅仅和 LCA 一起用的。当他们在和后缀数组（一个新的数据结构，它支持和

!

 假设一个算法预处理时间为"#$，查询时间为 #$。这个算法复杂度的标记为%"#$&#$'。我

们将用 



#&($来表示数组中索引 i 和 j 之间最小值的位置。 和 ) 的离树 T 根结点最远的公共祖先

用 



#&)$表示。

#$

 给定数组 *&!+,找出给定的两个索引间的最小值的位置。

)-"

 对每一对索引#&($，将 



#&($存储在 *&!+,*&!+,表中。普通的计算将得到一个

 &(3

 "#4*3%!355$

 43

 "#4*3%!355$

 "#(45,3(%!3(55$

 "#(+,%($

 (4(+,3

 

 (4(3

 6

 现在让我们看看怎样计算 



#&($。想法是遍历所有在区间中的 7#!$段的最小值，并且和区

间相交的前半和后半部分。为了计算上图中的 



8，并且获得最小值的位置。可以很容易的看出这个算法每一次查询不会超过 /:7#!$次操作。

 这个方法最大的有点是能够快速的编码（对于 TopCoder 类型的比赛），并且你可以把它改成问题的

动态版本（你可以在查询中间改变元素）。

;#;$-

 一个更好的方法预处理  是对 0

<

的长度的子数组进行动态规划。我们将使用数组 *&!+,

{

inti,j;



//initializeMfortheintervalswithlength1

for(i=0;i<N;i++)

M[i][0]=i;

//computevaluesfromsmallertobiggerintervals

for(j=1;1<<j<=N;j++)

for(i=0;i+(1<<j)-1<N;i++)

一旦我们预处理了这些值，让我们看看怎样使用它们去计算 



区间==(的块并且找到它们之间的最小值。设 <4#(+5,$.。为了计算 

使用下面的公式

So, the overall complexity of the algorithm is %.#!!$&.#,$'。

;

 为了解决 RMQ 问题我们也可以使用线段树。线段树是一个类似堆的数据结构，可以在基于区间数组

上用对数时间进行更新和查询操作。我们用下面递归方式来定义线段树的&(区间：