OI 必学：LCA 倍增算法

零、背景

在 OI 比赛中，我们经常会遇到各种关于树的相关问题。

前文《OI 必学：DFS 序》介绍 DFS 的应用时，可以发现，对于两点 (u, v) 链路的相关问题，都需要先找到它们的 LCA。

计算 LCA 的方法有很多种，如倍增法、Tarjan 离线算法、欧拉序 + RMQ 等。

但是观察涉及 LCA 的比赛题解源码，大家几乎都在使用倍增算法来求 LCA。

所以，本文重点介绍如何用倍增算法来求 LCA，并把整个思路从朴素做法一步步推导出来。

一、LCA 的定义

LCA 是有根树中的概念，全称为 Lowest Common Ancestor，即「最低公共祖先」。

具体来说，任意两个节点到根节点分别都有唯一的一条路径，这两条路径会有若干公共节点。从两个节点出发往上走，第一个相同的节点，就是它们的最低公共祖先，即 LCA。

如下图：
节点 u 到根节点的路径是红色的线。
节点 v 到根节点的路径是紫色的线。
这两条路径的公共祖先有节点 0 和节点 1，其中第一个公共祖先节点 1 就是 LCA。

二、LCA 的朴素算法

还是上面这张图，LCA 在两条路径上有什么共同的特点呢？
很容易发现：在两条路径上，从根节点到 LCA 的路径长度是相同的。

因此，可以定义一个函数 dep(a)，表示节点 a 到根节点的路径长度（深度）。
另外定义一个辅助函数 fa(a)，表示节点 a 的父节点。

现在要计算节点 u 和节点 v 的 LCA。
假设 dep(u) < dep(v)，则可以证明节点 v 本身肯定不是 LCA。
于是可以推出一个递推关系：LCA(u, v) = LCA(u, fa(v))。

基于这个推论，我们可以先把两个节点到根的路径长度「对齐」。
即比较 dep(u) 和 dep(v) 的大小：
如果 dep(u) > dep(v)，就让 u 往上走 dep(u) - dep(v) 步；否则就让 v 往上走 dep(v) - dep(u) 步，使得 dep(u) == dep(v)。

两个节点的深度对齐之后，只需要同时往上跳：
如果此时 u == v，那它们当前位置就是 LCA；
如果不相等，就让 u 和 v 一起往上走一步，再比较；如此循环，直到找到 LCA。

朴素算法的时间复杂度是 O(h)，其中 h 是树的高度。
在极端情况下（例如链状树），h 可以接近 n，就会比较慢。

三、LCA 的倍增算法

在朴素算法的基础上，很自然会想到：能不能用「二分」的思路来加快速度？

假设我们已经把两个节点的深度对齐了，现在要快速找到它们最近的公共祖先。
两个节点的祖先有一个很重要的特点：一旦某一层祖先相同，再往上的祖先也会一直相同。

如果我们能快速得到「向上走第 x 步」之后的祖先是谁，就可以套用二分的思路，从大步长往下试，不断逼近 LCA。

然而，节点到根的路径本质上是一条链表结构，没法像数组那样直接随机访问第 x 个祖先。
如果把每个节点从根到当前的所有祖先都存下来，空间复杂度就是 O(n * h)，在树比较高的时候会直接爆炸。

也就是说，可以先从两个极端情况来理解这个问题。
一种极端做法是「全部存下来」：每个节点都把从根到自己的所有祖先存下来，这样查询 LCA 时可以做到 O(1)，但是每个节点要存 O(h) 个祖先，整体空间复杂度是 O(n * h)。
另一种极端做法是「什么都不存」：完全不做预处理，每次查询时只能像朴素做法那样一层一层往上爬，这样空间是 O(1)，但时间就是 O(h)。

在实际的计算机环境中，如果空间爆炸，我们就必须想办法「少存一点」，用时间换空间。
最经典的设计就是「倍增」：只存「第 2^i 个祖先」。

具体做法是：预处理一个倍增表 st[i][v]，表示节点 v 的第 2^i 个祖先。
在文章《数据结构：ST 表-区间最值与 2 个注意事项》中已经简单介绍过「倍增」的实现与应用。
通过倍增，我们既可以把空间控制在 O(n log n)，又能把每次查询的时间复杂度降到 O(log n)。

倍增表的构建代码大致如下：

void BuildSparseTable(int n) {
  for (int i = 1; i < maxLog; i++) {
    for (int v = 0; v < n; v++) {
      int p = st[i - 1][v];
      if (p != -1) {
        st[i][v] = st[i - 1][p];
      } else {
        st[i][v] = -1;
      }
    }
  }
}

倍增表构建好之后，如何用它来二分找到最近公共祖先呢？

注意到倍增表本身就具备 2^i 这种「指数步长」的特性，从大到小枚举 i，本质上就是在做「按二进制拆分步长」的查找过程。

先假设两个节点 u 和 v 的深度已经对齐，并且 u != v。
此时可以从最大的 i 开始，一直枚举到 0，每次都尝试利用第 2^i 个祖先的信息来缩小答案范围。
具体地说，如果在某个 i 上有 st[i][u] != st[i][v]，就把 u 和 v 都同时跳到它们的第 2^i 个祖先处；如果在这一层它们的祖先仍然相同，就跳过这一层，继续尝试更小的 i。

直觉上可以这样理解这一过程。
当 u 和 v 在第 2^i 层的祖先已经不相同时，LCA 一定处在这两层祖先的上方，但又不会高到超过它们的第 2^(i+1) 层祖先，所以我们可以放心地让它们都向上跳 2^i 步，从而缩小可能范围。
而当在某一层它们的祖先仍然相同，就说明 LCA 还在更上方，这一层的信息对区分它们没有帮助，可以直接跳过，继续向上尝试。

对应的代码写法也很简洁：

for (int i = maxLog - 1; i >= 0; i--) {
  if (st[i][u] != st[i][v]) {
    u = st[i][u];
    v = st[i][v];
  }
}
return st[0][u];

这里还有一个关键细节：如何对齐两个节点的高度？

这一步同样可以利用倍增表来完成。
我们可以把「向上跳 k 步」这个操作拆成若干个 2^i 的组合，即把 k 按二进制分解，用若干次倍增来完成一次长距离跳跃：

// 让节点 u 向上跳 k 步，返回跳到的节点编号
int PreKthAncestor(int u, int k) {
  for (int i = maxLog - 1; k && i >= 0; i--) {
    if (k & (1 << i)) {
      u = st[i][u];
      k ^= (1 << i);
    }
  }
  return u;
}

实际使用时，求 LCA 的完整流程大致可以分为三个步骤。
首先，用 DFS 或 BFS 预处理整棵树，求出每个节点的深度和父节点。
接着，根据父节点信息构建倍增表 st[i][v]。
最后，对于任意一对查询点 (u, v)，先用上面的函数把它们的深度对齐，再按照从大到小的 i 来同时提升它们，最终得到的共同父节点就是 LCA。

四、最后

LCA 和倍增一样，都是非常基础、但极其高频的算法工具。

例如在上一篇《OI 必学：DFS 序》中，那些路径相关的问题，基本都需要先求出 LCA，把路径拆成两条到根的路径来处理。
后面还会分享的「虚树」相关内容，也同样会大量用到 LCA。

树上的很多问题，都会绕不开 LCA。等讲到具体题目和算法时，再结合实例来演示 LCA 的具体用法。

《完》

-EOF-

本文公众号：天空的代码世界
个人微信号：tiankonguse
公众号 ID：tiankonguse-code