LCA问题的跳表算法 >> NoAlGo博客

LCA问题的跳表算法 » NoAlGo博客
LCA问题的一般形式：给定一棵有根树，给出若干个查询，每个查询要求指定节点u和v的最近公共祖先。
LCA问题有两类解决思路:

• 在线算法，每次读入一个查询，处理这个查询，给出答案。
• 离线算法，一次性读入所有查询，统一进行处理，给出所有答案

跳表算法是在线算法，其需要O(nlogn)的复杂度进行初始化，然后每进行一个查询需要O(logn)复杂度进行解答。

使用跳表解决LCA问题时，对每个节点i维护了一个数组anc[i][j]，表示i的第2^j个祖先的节点。有了这个数组后，节点x沿着树往上跳2^k层之后，就变成了节点anc[x][k]。当待查询的两个节点u和v在同一层时，我们把uv每次向上跳2的幂次的距离，最后同时到达了u和v的LCA节点。

可以知道，由于每次跳的距离都是2的幂，如果把uv和其LCA节点间的深度差用二进制表示，则其中的每个出现1的位置就是uv每次所要跳的距离。比如，要查找5和6的LCA，则把5和6都往上跳2^1层，同时到达0，0即为所求LCA。

但如果0上面还有很多节点，则5和6同时往上跳比2更大的距离（如4）时，也会到达同样的节点，但并不是LCA（不是最近）。

为了避免这个问题，我们在跳的时候不要让他们到达相同的节点，这样就不会跳过头了。最终u和v会跳到其LCA的下一层，u和v的父亲就是他们的LCA。即，查找5和6的LCA时，5最终会跳到1，6会跳到3，它们的父亲0为要求的LCA。

当待查询的两个节点u和v不在同一层时，假如u的层数比较深。这是我们先把u跳到和v同一层的祖先中，然后再使用上述相同层的方法。把u每次往上跳2的幂次的层数，如果跳了之后在v的上方了，则不跳，否则就跳。可以知道，将u和v之间的深度差用二进制表示，则其中每个出现1的位置就是要跳的距离。比如，要查找7和6的LCA，首先把7往上跳到和6同一层的5中，然后再使用上述方法求5和6的LCA即可。

Read full article from LCA问题的跳表算法 » NoAlGo博客