最近公共祖先的倍增求法总结

高效求解最近公共祖先的价值是巨大的。其中最简单的应用就是求解树任意两点之间的距离。

本文递交已结束。

对于要求解节点 $u$ 与节点 $v$ 的最近公共祖先，朴素的思想是将 $u$ 与 $v$ 同时向上跳，并标记跳到过的点如果当任意一个点第一次跳到某一个被标记过的点时即为这两点的最近公共祖先。当树退化成链时求解的复杂度变为了 $O(n)$ 。利用倍增思想优化是十分简单的，“即将 $u$ 、 $v$ 成倍地向上跳”。但是为了方便从上向下跳更为简单。首先将两点调至同一高度，由于知道高度差，这一步只需要对高度差进行二进制拆分即可。然后，将两点向上跳 $2^{\log n}$ （即为一个极大的值，超过根就记为根）步，此时两点所到之处一定是相同，那么则说明跳多了，则将两点向上跳 $2^{\log n-1}$ 步，此时如果两节点不在同一位置这说明它们的公共祖先在它们原来位置的 $2^{\log n-1}$ 与 $2^{\log n}$ 之间。重复上述过程则可以在 $\Theta(\log n)$ 的级别下求出最近公共祖先。考虑上述算法的过程，只有在所到之点不同时两点才会向上跳即更新起点的位置，那么算法最后一定会停留在两点起点不相同但向上跳 $2^0$ 所到之点就相同的位置，即为最近公共祖先的儿子，最后返回答案时返回其父亲即可。

还有一种效率极高但空间复杂度为 $O(n^2)$ 的最近公共祖先的算法。大概的思路是从叶子节点开始灌水，但空间复杂度极高几乎没用。

本文采用署名-非商业性使用-相同方式共享 4.0 国际许可协议，转载请注明出处。