c***y
发帖数: 560 | 1 根据这个link:
http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor#Range_Minimum_Query_%28RMQ%29
LCA的最优解似乎还是O(N) in both time and space complexity
似乎basic idea is transform a tree to an array in Euler Tour, then conduct
RMQ between this range.
如果这样，假设找node1&node2的LCA, 为啥不求得root-node1 & root-node2 path, 然
后找他们的最深交集呢? 难道是因为如果pre-build RMQ,可以support任意两点之间的
LCA？
谢谢讨论, thanks. | b****r
发帖数: 1272 | 2 it's restricted RMQ O(1) | A*******k
发帖数: 72 | 3 基于Euler tour的RMQ的特点是任何两个相邻的数之间的差异是1，有O(1)的解法。所以
processing整个树用了O(n)时间后，每次query只需要constent time。是不是比每次
query都要找两个路径用log(n)的时间要好呢？呵呵。
另外，LCA和RMQ两个问题可以相互转化。实际上对于general的RMQ问题，可以先转化成
LCA问题，然后再通过Eular tour转化成restrict RMQ 问题，然后O(1)就可以解决了。
不知道说清楚了没有。
【在 c***y 的大作中提到】
: 根据这个link:
: http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor#Range_Minimum_Query_%28RMQ%29
: LCA的最优解似乎还是O(N) in both time and space complexity
: 似乎basic idea is transform a tree to an array in Euler Tour, then conduct
: RMQ between this range.
: 如果这样，假设找node1&node2的LCA, 为啥不求得root-node1 & root-node2 path, 然
: 后找他们的最深交集呢? 难道是因为如果pre-build RMQ,可以support任意两点之间的
: LCA？
: 谢谢讨论, thanks.
|
|
