最低共同祖先

Question

我的问题是树中有大量的节点和许多查询。是否有一种算法，它进行预处理，使查询能够在恒定的时间内得到答复。

我研究了使用RMQ的LCA，但我不能使用该技术，因为我不能对树中的这么多节点使用数组。

如果知道它是满二叉树，节点之间的关系如上所示，那么有人能给我一个高效的实现来快速回答许多查询。

但是当有很多查询时，这种算法非常耗时，因为在最坏的情况下，我可能必须遍历30的高度（树的最大高度）才能到达根（最坏的情况）。

Answer 1

如果您用二进制表示这两个索引，那么可以通过两个步骤找到LCA：

1. 右移较大的数字，直到前导1位与另一个数字在同一位置。
2. 向右移动两个数字，直到它们相同。

第一步可以通过获得数字的对数基数2，并将较大的数字向右移动差值来完成：

if a>b:
    a = shift_right(a,log2(a)-log2(b))
else:
    b = shift_right(b,log2(b)-log2(a))

if a==b:
    return a
else:
    return shift_right(a,log2(xor(a,b))+1)