最小公共祖先（LCA）问题的在线倍增算法
字数 2399 2025-12-17 08:04:46

最小公共祖先（LCA）问题的在线倍增算法

题目描述
给定一棵包含 \(n\) 个节点的有根树（根节点已知），以及 \(m\) 次查询。每次查询给出两个节点 \(u\) 和 \(v\)，需要快速求出它们的最近公共祖先（Lowest Common Ancestor, LCA），即深度最大（距离根节点最远）的、同时是 \(u\) 和 \(v\) 祖先的节点。
要求设计一个算法，在 \(O(n \log n)\) 的预处理时间后，能够以 \(O(\log n)\) 的时间复杂度在线回答每次查询。

核心思路
在线倍增算法（Binary Lifting）的核心思想是“跳跃”与“二分”。预处理中，我们为每个节点 \(u\) 记录其向上 \(2^k\) 层的祖先节点。查询时，通过不断调整 \(u\) 和 \(v\) 到同一深度，再一起向上“试探跳跃”，最终精确找到它们的最近公共祖先。

详细步骤

步骤1：问题模型与输入

  • 假设树以邻接表形式存储，节点编号为 \(1\) 到 \(n\)，根节点为 \(root\)。
  • 需要预处理的数据结构：
    • \(depth[u]\)：节点 \(u\) 的深度（根节点深度为 \(0\)）。
    • \(up[u][k]\)：节点 \(u\) 向上走 \(2^k\) 步到达的祖先节点。如果 \(u\) 向上 \(2^k\) 步会超出根节点，则 \(up[u][k] = 0\)（假设节点编号从 \(1\) 开始，\(0\) 表示空节点）。

步骤2：深度优先搜索（DFS）预处理深度与直接父节点

  • 从根节点开始进行 DFS 遍历，初始化：
    • 对根节点 \(root\)：\(depth[root] = 0\)，\(up[root][0] = 0\)（没有父节点）。
    • 对 \(u\) 的每个子节点 \(v\)：
      • \(depth[v] = depth[u] + 1\)
      • \(up[v][0] = u\)（\(v\) 向上 \(2^0 = 1\) 步就是其直接父节点）。
  • 这一步时间复杂度 \(O(n)\)，同时得到了每个节点的深度和直接父节点。

步骤3：倍增表的递推计算

  • 设 \(K\) 为满足 \(2^K \ge n\) 的最小整数，通常 \(K = \lceil \log_2 n \rceil\)。\(up\) 数组的第二维大小为 \(K+1\)。
  • 递推公式：\(up[u][j] = up[ up[u][j-1] ][j-1]\)
    • 含义：节点 \(u\) 向上 \(2^j\) 层的祖先，等于其向上 \(2^{j-1}\) 层的祖先再向上 \(2^{j-1}\) 层。
    • 边界：当 \(j=0\) 时，\(up[u][0]\) 已在 DFS 中求得。
  • 计算顺序：先枚举 \(j\) 从 \(1\) 到 \(K\)，再枚举节点 \(u\) 从 \(1\) 到 \(n\)。
  • 时间复杂度：\(O(n \log n)\)。

步骤4：查询最近公共祖先（LCA）
输入查询节点 \(u\) 和 \(v\)，执行以下三步：

  1. 调整到同一深度
    如果 \(depth[u] < depth[v]\)，交换 \(u\) 和 \(v\)，确保 \(u\) 是深度较大的节点。
    然后计算差值 \(diff = depth[u] - depth[v]\)。
    从高到低枚举 \(j\) 从 \(K\) 到 \(0\)：
    如果 \(diff\) 的二进制表示中第 \(j\) 位为 \(1\)（即 \(diff \ge 2^j\)），则令 \(u = up[u][j]\)，相当于向上跳 \(2^j\) 层。
    这一步结束后，\(u\) 和 \(v\) 深度相同。

  2. 特判：如果 \(u == v\)，则 LCA 就是 \(u\)
    说明 \(u\) 是 \(v\) 的祖先（或相反），直接返回。

  3. 同时向上跳跃
    从高到低枚举 \(j\) 从 \(K\) 到 \(0\)：
    如果 \(up[u][j] \neq up[v][j]\)，说明 \(u\) 和 \(v\) 向上 \(2^j\) 步的祖先不同，则让 \(u\) 和 \(v\) 同时向上跳 \(2^j\) 步（\(u = up[u][j]\)，\(v = up[v][j]\)）。
    这一步结束时，\(u\) 和 \(v\) 是 LCA 的两个直接子节点（即它们的父节点就是 LCA）。

  4. 返回 LCA
    LCA 就是 \(up[u][0]\)（或 \(up[v][0]\)，两者相等）。

  • 每一步的时间复杂度是 \(O(\log n)\)。

步骤5：算法正确性解释

  • 第一步通过二进制分解，可以精确向上跳 \(diff\) 层，使 \(u\) 和 \(v\) 深度相同。
  • 第三步的关键在于，当 \(up[u][j] \neq up[v][j]\) 时才跳跃。这保证了 \(u\) 和 \(v\) 不会跳过 LCA，而是最终停留在 LCA 的下一层。因为从高到低枚举 \(j\)，相当于“试探”最大可跳步数，避免跳过头。
  • 最后一步返回父节点，即为所求。

步骤6：复杂度分析

  • 预处理：DFS 遍历 \(O(n)\)，倍增表递推 \(O(n \log n)\)，总 \(O(n \log n)\)。
  • 每次查询：\(O(\log n)\)。
  • 空间复杂度：\(O(n \log n)\) 用于存储 \(up\) 表。

步骤7：实例演示
考虑一棵有根树，根为 1。
预处理得到 \(depth\) 和 \(up\) 表。
查询 LCA(5, 7)：
假设 depth[5]=3, depth[7]=4，先交换使 u=7, v=5。
diff=1，跳 2^0=1 步，u 变为 6（与 v=5 同深度 3）。
因为 u≠v，从 j=K 向下试探：
若 up[6][j]≠up[5][j]，则跳跃。
最后 u 和 v 分别变为 2 和 3，它们的父节点 1 就是 LCA。

总结
在线倍增算法通过“预处理跳跃表”与“二进制分解跳跃”，在 \(O(n \log n)\) 预处理后，实现了 \(O(\log n)\) 的快速 LCA 查询，是解决树上最近公共祖先问题的经典在线算法。

最小公共祖先（LCA）问题的在线倍增算法 题目描述 给定一棵包含 $n$ 个节点的有根树（根节点已知），以及 $m$ 次查询。每次查询给出两个节点 $u$ 和 $v$，需要快速求出它们的 最近公共祖先 （Lowest Common Ancestor, LCA），即深度最大（距离根节点最远）的、同时是 $u$ 和 $v$ 祖先的节点。 要求设计一个算法，在 $O(n \log n)$ 的预处理时间后，能够以 $O(\log n)$ 的时间复杂度在线回答每次查询。 核心思路 在线倍增算法（Binary Lifting）的核心思想是“跳跃”与“二分”。预处理中，我们为每个节点 $u$ 记录其向上 $2^k$ 层的祖先节点。查询时，通过不断调整 $u$ 和 $v$ 到同一深度，再一起向上“试探跳跃”，最终精确找到它们的最近公共祖先。 详细步骤 步骤1：问题模型与输入 假设树以邻接表形式存储，节点编号为 $1$ 到 $n$，根节点为 $root$。 需要预处理的数据结构： $depth[ u ]$：节点 $u$ 的深度（根节点深度为 $0$）。 $up[ u][ k]$：节点 $u$ 向上走 $2^k$ 步到达的祖先节点。如果 $u$ 向上 $2^k$ 步会超出根节点，则 $up[ u][ k ] = 0$（假设节点编号从 $1$ 开始，$0$ 表示空节点）。 步骤2：深度优先搜索（DFS）预处理深度与直接父节点 从根节点开始进行 DFS 遍历，初始化： 对根节点 $root$：$depth[ root] = 0$，$up[ root][ 0 ] = 0$（没有父节点）。 对 $u$ 的每个子节点 $v$： $depth[ v] = depth[ u ] + 1$ $up[ v][ 0 ] = u$（$v$ 向上 $2^0 = 1$ 步就是其直接父节点）。 这一步时间复杂度 $O(n)$，同时得到了每个节点的深度和直接父节点。 步骤3：倍增表的递推计算 设 $K$ 为满足 $2^K \ge n$ 的最小整数，通常 $K = \lceil \log_ 2 n \rceil$。$up$ 数组的第二维大小为 $K+1$。 递推公式：$up[ u][ j] = up[ up[ u][ j-1] ][ j-1 ]$ 含义：节点 $u$ 向上 $2^j$ 层的祖先，等于其向上 $2^{j-1}$ 层的祖先再向上 $2^{j-1}$ 层。 边界：当 $j=0$ 时，$up[ u][ 0 ]$ 已在 DFS 中求得。 计算顺序：先枚举 $j$ 从 $1$ 到 $K$，再枚举节点 $u$ 从 $1$ 到 $n$。 时间复杂度：$O(n \log n)$。 步骤4：查询最近公共祖先（LCA） 输入查询节点 $u$ 和 $v$，执行以下三步： 调整到同一深度 如果 $depth[ u] < depth[ v ]$，交换 $u$ 和 $v$，确保 $u$ 是深度较大的节点。 然后计算差值 $diff = depth[ u] - depth[ v ]$。 从高到低枚举 $j$ 从 $K$ 到 $0$： 如果 $diff$ 的二进制表示中第 $j$ 位为 $1$（即 $diff \ge 2^j$），则令 $u = up[ u][ j ]$，相当于向上跳 $2^j$ 层。 这一步结束后，$u$ 和 $v$ 深度相同。 特判：如果 $u == v$，则 LCA 就是 $u$ 说明 $u$ 是 $v$ 的祖先（或相反），直接返回。 同时向上跳跃 从高到低枚举 $j$ 从 $K$ 到 $0$： 如果 $up[ u][ j] \neq up[ v][ j]$，说明 $u$ 和 $v$ 向上 $2^j$ 步的祖先不同，则让 $u$ 和 $v$ 同时向上跳 $2^j$ 步（$u = up[ u][ j]$，$v = up[ v][ j ]$）。 这一步结束时，$u$ 和 $v$ 是 LCA 的两个直接子节点（即它们的父节点就是 LCA）。 返回 LCA LCA 就是 $up[ u][ 0]$（或 $up[ v][ 0 ]$，两者相等）。 每一步的时间复杂度是 $O(\log n)$。 步骤5：算法正确性解释 第一步通过二进制分解，可以精确向上跳 $diff$ 层，使 $u$ 和 $v$ 深度相同。 第三步的关键在于，当 $up[ u][ j] \neq up[ v][ j ]$ 时才跳跃。这保证了 $u$ 和 $v$ 不会跳过 LCA，而是最终停留在 LCA 的下一层。因为从高到低枚举 $j$，相当于“试探”最大可跳步数，避免跳过头。 最后一步返回父节点，即为所求。 步骤6：复杂度分析 预处理：DFS 遍历 $O(n)$，倍增表递推 $O(n \log n)$，总 $O(n \log n)$。 每次查询：$O(\log n)$。 空间复杂度：$O(n \log n)$ 用于存储 $up$ 表。 步骤7：实例演示 考虑一棵有根树，根为 1。 预处理得到 $depth$ 和 $up$ 表。 查询 LCA(5, 7)： 假设 depth[ 5]=3, depth[ 7 ]=4，先交换使 u=7, v=5。 diff=1，跳 2^0=1 步，u 变为 6（与 v=5 同深度 3）。 因为 u≠v，从 j=K 向下试探： 若 up[ 6][ j]≠up[ 5][ j ]，则跳跃。 最后 u 和 v 分别变为 2 和 3，它们的父节点 1 就是 LCA。 总结 在线倍增算法通过“预处理跳跃表”与“二进制分解跳跃”，在 $O(n \log n)$ 预处理后，实现了 $O(\log n)$ 的快速 LCA 查询，是解决树上最近公共祖先问题的经典在线算法。