发布于 ,更新于 

倍增求LCA/最近共同祖先

倍增求 LCA 是一种不太高效1的求 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}\) 即可。

  1. 不如树剖好想好写,也不如树剖快。真要高效的话,建议欧拉序 RMQ 复杂度解决。↩︎