倍增求LCA/最近共同祖先

倍增求 LCA 是一种不太高效¹的求 LCA 算法，时间复杂度为 \(\operatorname{O}(n \log n) \sim \operatorname{O}(\log n)\)

原理

初始

维护一个 \(fa_{i,x}\) 表示 \(x\) 往根节点走 \(2^i\) 步到达的节点。

• 初始化时 \(fa_{0,x} = father_x\)
• 更新为 \(fa_{i,x} = fa_{i-1,fa_{i-1,x}}\)

查询

中心思想是利用二进制向上跳。
假设目前要查询 a 号节点和 b 号节点的 LCA，将较深节点设为a，较浅设为b，即：

• 首先将 a 向上跳到和 b 同一高度，若此时 a = b，直接返回 b 即可，即 b 为 a 的一个直接父亲，LCA 也一定是 b。
• 否则将两个节点同时往上跳，\(i\) 从大到小，每次跳 \(2^i\)，规则如下：
  1. 如果跳完两个节点相同，即找到了一个共同祖先，则不跳，因为此时不能确定这个共同祖先是不是最近的。
  2. 否则就继续同时往上跳，最终返回 \(fa_{0,a}\) 即可。