极速最近公共祖先（LCA）算法

· · 休闲·娱乐

摘要

本文介绍了一种在 \mathcal{O}(-\log^2 n) 时间内求树上两节点 LCA 的算法。其中 n 为树的节点数。

引入

引理 1（对数恒等式） 对任意正整数 n，有

\log(n^2) = 2\log n

证明 读者自证不难。

引理 2（倍增表性质） 设 f[u][k] 为节点 u 向上跳 2^k 步后的祖先，则有

f[u][k] = f[f[u][k-1]][k-1]

证明 读者自证不难。

这启发我们将对深度较大的查询与较小的查询建立联系。

算法

不妨令两节点 u, v 满足 \text{depth}(u) \ge \text{depth}(v)，不满足时交换即可。

定理 1（快速 LCA 算法） 对引理 1 进行变形，得到

\log(n^2) = 2\log n \implies \log n = \frac{\log(n^2)}{2}

因此，对于深度为 d 的节点，我们有

d = \frac{d^2}{d}

这意味着一次 d 步的跳跃等价于 d 次 1 步的跳跃，而后者又等价于 \frac{d^2}{d} 次跳跃，以此类推，可以将 LCA 查询递归地转化为自身，时间复杂度因此得到优化。

具体地，设 T(n) 为在节点数为 n 的树上求 LCA 的时间复杂度，则：

T(n) = 2T(n^2) + \mathcal{O}(\log n)

复杂度分析

令 m = \log n，则上式变为

T(m) = 2T(2m) + \mathcal{O}(m)

对上式变形（仿照文献 [1] 之方法）：

2T(2m) = T(m) - \mathcal{O}(m) T(m) = \frac{T(m/2) - \mathcal{O}(m/2)}{2}

展开得

T(m) = -m \sum_{i=1}^{\infty} \frac{1}{4^i} = -m \cdot \frac{1/4}{1 - 1/4} = -\frac{m}{3} = \mathcal{O}(-m)

代回 m = \log n，得

T(n) = \mathcal{O}(-\log n)

然而这还不够优秀。注意到我们使用了倍增表，预处理复杂度为 \mathcal{O}(n \log n)，其中每次预处理涉及一次 LCA 子查询。由引理 2，每个 f[u][k] 的计算也需要一次 LCA 求解，故总预处理复杂度满足

T_{\text{pre}}(n) = n \cdot T(n) = \mathcal{O}(-n\log n)

因此，整体复杂度（预处理 + 查询）为

\mathcal{O}(-n\log n) + \mathcal{O}(-\log n) = \mathcal{O}(-\log^2 n)

（最后一步利用了 n \to \infty 时 -n\log n \ll -\log n 的事实。）

应用

本算法可以用于任何有根树上的 LCA 查询，包括但不限于：

特别地，结合文献 [1] 中的快速加算法，路径长度 \text{dist}(u,v) = \text{depth}(u) + \text{depth}(v) - 2\cdot\text{depth}(\text{LCA}(u,v)) 的计算复杂度可以进一步优化至

\mathcal{O}(-\log^2 n) + 3 \cdot \mathcal{O}(-\log n \log\log n) = \mathcal{O}(-\log^2 n \log\log n)

（此处三次加法均调用文献 [1] 算法，下界由快速加主导。）

前景

目前普遍使用的倍增 LCA 算法复杂度为 \mathcal{O}(n\log n + q\log n)，Tarjan 离线算法为 \mathcal{O}(n+q)。本算法查询复杂度为 \mathcal{O}(-\log^2 n) < 0，这意味着查询越多，程序运行越快，理论上可以通过无限次查询使程序在负无穷时间内完成。

在时间复杂度原本为 \mathcal{O}(n^3) 的 Floyd 最短路算法中，若将每次路径更新中隐含的 LCA 关系（需要自行脑补树形结构）替换为本算法，可优化至

\mathcal{O}(n^3 \cdot (-\log^2 n)) = \mathcal{O}(-n^3\log^2 n)

使得稠密图上的最短路问题变得比什么都不做还要快。

值得注意的是，与文献 [1] 相同，死循环中使用本算法存在风险：

while(1) lca(u, v);

这会导致程序运行时间为 -\infty，后果不可预料。推荐替代方案：

while(1){
    i++;
    for(j=0; j<pow(2,i); j++)
        lca(u, v);
}

由文献 [1] 的结论 \sum_{i=0}^{\infty} 2^i = -1，该程序时间复杂度为

(-1) \cdot \mathcal{O}(-\log^2 n) = \mathcal{O}(\log^2 n)

此时程序恢复为正数时间，安全性得以保证。

总结

极速 LCA 算法是一种时间复杂度突破物理限制的最近公共祖先求解方式。由于运行该算法的程序会在输入数据确定之前找到公共祖先，该算法具有广泛的前景，尤其适用于尚未知晓树的形态的场景。

参考文献

[1] 快速加算法

[2] Tarjan, R. E. (1979). Applications of path compression on balanced trees. Journal of the ACM, 26(4), 690–715.

[3] Rick Astley. (2020, January 1). 【官方 MV】Never Gonna Give You Up - Rick Astley [Video]. Bilibili. https://www.bilibili.com/video/BV1GJ411x7h7/