Range Minimum Query and Lowest Common Ancestor[翻译]1
需积分: 0 23 浏览量
2022-08-08
19:42:09
上传
评论
收藏 120KB DOCX 举报
Range Minimum Query and Lowest Common Ancestor[翻译]
2007-10-23 09:38 by 农夫三拳, 6076 阅读, 13 评论, 收藏, 编辑
Range Minimum Query and Lowest Common Ancesto
r
【原文见 http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=lo
westCommonAncestor】
作者： By danielp
Topcoder Member
翻
译： 农夫三拳@seu
Introduction
Notations
Range Minimum Query (RMQ)
Trivial algorithms for RMQ
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
Introduction
在一棵树中查找一对结点的最近公共祖先(LCA)的问题在 20 世纪末期已经被仔细的研
究过了，并且它现在已经成为算法中图论的基本算法了。这个问题之所以有趣并不是因为处
理它的算法很有技巧，而是因为它在字符串处理和生物学计算中的广泛应用，例如，当 LCA
和后缀树或者其他树形结构在一起使用时。Harel and Tarjan 是首先深入研究这个问题的
人，他们得出：在对输入树 LCA 进行线性处理后，查询可以在常数时间内得到答案。他们
的工作已经得到了广泛的延伸，这篇教程将展示一些有趣的方法，而它们还也可以用在其他
的问题上。
让我们考虑一个不太抽象的 LCA 的例子：生命树。地球上当前的居住者是由其他物种
进化而来已经是一个不争的事实。这种进化结构可以表示成一棵树，其中节点表示物种，而
它的孩子结点表示从该物种直接进化得到的物种。现在通过在树中查找一些结点的 LCA 把
具有相似特征的物种划分成组，我们可以找出两个物种共同的祖先，并且我们可以知道它们
所拥有的相似特征是来自于那个祖先。
剩余22页未读，继续阅读
评论0