最小公共祖先（LCA）问题的 RMQ 解法
字数 2748 2025-12-16 18:09:48

最小公共祖先（LCA）问题的 RMQ 解法

题目描述

给定一棵有根树，树中有 \(n\) 个节点，节点编号为 \(1\) 到 \(n\)。有 \(m\) 次查询，每次查询给出两个节点 \(u\) 和 \(v\)，要求求出节点 \(u\) 和 \(v\) 的最小公共祖先（Lowest Common Ancestor, LCA）。
最小公共祖先是指，在树中同时是 \(u\) 和 \(v\) 的祖先的节点中，深度最大的那个节点（深度定义为从根节点到该节点的路径上的边数）。
要求实现一种算法，能够对树进行预处理，使得每次查询可以在 \(O(1)\) 时间内完成。

解题思路

一种经典且高效的解法是：

  1. 对树进行一次深度优先遍历，记录遍历过程中访问节点的顺序，并同时记录每个节点的深度。
  2. 在遍历过程中，记录每个节点第一次被访问时在遍历序列中的位置。
  3. 任意两个节点 \(u\) 和 \(v\) 的 LCA，就对应在深度优先遍历序列中，从 \(u\) 第一次出现的位置到 \(v\) 第一次出现的位置这一段区间内，深度最小的节点。
  4. 于是，原问题转化为：在遍历序列的某个区间中，查询深度最小的节点。这是一个经典的区间最小值查询（Range Minimum Query, RMQ）问题。
  5. 通过稀疏表（Sparse Table）对 RMQ 进行预处理，即可在 \(O(1)\) 时间内回答每次查询。

详细步骤

步骤 1：深度优先遍历与序列生成

  • 从根节点开始进行深度优先遍历。
  • 遍历时，每当进入一个节点，就将其加入序列 \(euler\) 中，并记录这个节点的深度。
  • 同时，记录每个节点第一次出现在 \(euler\) 序列中的位置，记为 \(first[u]\)。

例如，对于下面的树（根为 1）：

        1
       / \
      2   3
     / \
    4   5

一种可能的 DFS 遍历顺序是：1 → 2 → 4 → 2 → 5 → 2 → 1 → 3 → 1。
对应的 \(euler\) 序列和深度序列如下：

  • \(euler\) 序列：[1, 2, 4, 2, 5, 2, 1, 3, 1]
  • 深度序列： [0, 1, 2, 1, 2, 1, 0, 1, 0]
  • \(first\) 数组：
    \(first[1] = 0\)（下标从0开始）
    \(first[2] = 1\)
    \(first[3] = 7\)
    \(first[4] = 2\)
    \(first[5] = 4\)

步骤 2：转化为 RMQ 问题

  • 对于查询 \(LCA(u, v)\)，我们取 \(u\) 和 \(v\) 在 \(euler\) 序列中第一次出现的位置：\(L = first[u]\)，\(R = first[v]\)。
  • 为方便处理，我们假设 \(L \le R\)，如果不满足则交换。
  • 在 \(euler\) 序列的区间 \([L, R]\) 中，找到深度最小的节点，这个节点就是 \(u\) 和 \(v\) 的 LCA。
  • 为什么？因为深度优先遍历的性质保证了：在 \(euler\) 序列中，\(u\) 和 \(v\) 的 LCA 一定出现在 \(u\) 和 \(v\) 的第一次出现位置之间，且它是这个区间内深度最小的节点（因为 LCA 深度最浅，且 DFS 一定会访问到它）。

步骤 3：用稀疏表处理 RMQ

稀疏表可以在 \(O(1)\) 时间内回答区间最小值查询，前提是进行 \(O(n \log n)\) 的预处理。

  • 设 \(depth[i]\) 是 \(euler[i]\) 对应节点的深度。
  • 定义 \(st[k][i]\) 表示从 \(i\) 开始，长度为 \(2^k\) 的区间中，深度最小值的下标。
  • 预处理递推公式：
    • 初始：\(st[0][i] = i\)（长度为1的区间，最小值就是自己）
    • 递推：\(st[k][i] = \arg\min(depth[st[k-1][i]], depth[st[k-1][i+2^{k-1}]])\)
  • 查询区间 \([L, R]\) 时：
    • 设 \(k = \lfloor \log_2 (R - L + 1) \rfloor\)
    • 比较区间 \([L, L+2^k-1]\) 和 \([R-2^k+1, R]\) 这两个区间的最小值，取深度更小的那个下标即可。

步骤 4：查询 LCA

  1. 输入 \(u, v\)。
  2. 令 \(L = first[u]\)，\(R = first[v]\)，如果 \(L > R\) 则交换。
  3. 在区间 \([L, R]\) 上查询深度最小的节点下标 \(idx\)。
  4. 答案就是 \(euler[idx]\)。

复杂度分析

  • 预处理：
    • DFS 遍历：\(O(n)\)
    • 稀疏表构建：\(O(n \log n)\)
  • 每次查询：\(O(1)\)
  • 总复杂度：\(O(n \log n + m)\)

举例说明

还是上面的树，查询 LCA(4, 5)：

  • \(first[4] = 2\)，\(first[5] = 4\)，区间为 [2, 4]。
  • \(euler[2..4] = [4, 2, 5]\)，对应的深度为 [2, 1, 2]。
  • 深度最小的是深度为 1 的节点 \(euler[3] = 2\)（注意下标 3 对应节点 2）。
  • 所以 LCA(4, 5) = 2，正确。

查询 LCA(4, 3)：

  • \(first[4] = 2\)，\(first[3] = 7\)，区间为 [2, 7]。
  • \(euler[2..7] = [4, 2, 5, 2, 1, 3]\)，深度为 [2, 1, 2, 1, 0, 1]。
  • 深度最小的是深度为 0 的节点 \(euler[6] = 1\)。
  • 所以 LCA(4, 3) = 1，正确。

关键点

  • 将 LCA 问题转化为 RMQ 问题的关键在于深度优先遍历序列和每个节点第一次出现位置的记录。
  • 稀疏表是解决静态 RMQ 问题的高效数据结构，允许 \(O(1)\) 查询。
  • 此方法适用于静态树（树的结构不会改变），预处理后可以高效回答大量查询。

这个解法是 LCA 问题的经典方法之一，在算法竞赛和实际应用中都非常高效。

最小公共祖先（LCA）问题的 RMQ 解法 题目描述 给定一棵有根树，树中有 \( n \) 个节点，节点编号为 \( 1 \) 到 \( n \)。有 \( m \) 次查询，每次查询给出两个节点 \( u \) 和 \( v \)，要求求出节点 \( u \) 和 \( v \) 的 最小公共祖先 （Lowest Common Ancestor, LCA）。 最小公共祖先是指，在树中同时是 \( u \) 和 \( v \) 的祖先的节点中，深度最大的那个节点（深度定义为从根节点到该节点的路径上的边数）。 要求实现一种算法，能够对树进行 预处理 ，使得每次查询可以在 \( O(1) \) 时间内完成。 解题思路 一种经典且高效的解法是： 对树进行一次 深度优先遍历 ，记录遍历过程中访问节点的顺序，并同时记录每个节点的深度。 在遍历过程中，记录每个节点 第一次被访问时 在遍历序列中的位置。 任意两个节点 \( u \) 和 \( v \) 的 LCA，就对应在深度优先遍历序列中，从 \( u \) 第一次出现的位置到 \( v \) 第一次出现的位置这一段区间内， 深度最小的节点 。 于是，原问题转化为：在遍历序列的某个区间中，查询深度最小的节点。这是一个经典的 区间最小值查询 （Range Minimum Query, RMQ）问题。 通过 稀疏表 （Sparse Table）对 RMQ 进行预处理，即可在 \( O(1) \) 时间内回答每次查询。 详细步骤 步骤 1：深度优先遍历与序列生成 从根节点开始进行深度优先遍历。 遍历时，每当进入一个节点，就将其加入序列 \( euler \) 中，并记录这个节点的深度。 同时，记录每个节点 第一次 出现在 \( euler \) 序列中的位置，记为 \( first[ u ] \)。 例如，对于下面的树（根为 1）： 一种可能的 DFS 遍历顺序是：1 → 2 → 4 → 2 → 5 → 2 → 1 → 3 → 1。 对应的 \( euler \) 序列和深度序列如下： \( euler \) 序列：[ 1, 2, 4, 2, 5, 2, 1, 3, 1 ] 深度序列： [ 0, 1, 2, 1, 2, 1, 0, 1, 0 ] \( first \) 数组： \( first[ 1 ] = 0 \)（下标从0开始） \( first[ 2 ] = 1 \) \( first[ 3 ] = 7 \) \( first[ 4 ] = 2 \) \( first[ 5 ] = 4 \) 步骤 2：转化为 RMQ 问题 对于查询 \( LCA(u, v) \)，我们取 \( u \) 和 \( v \) 在 \( euler \) 序列中第一次出现的位置：\( L = first[ u] \)，\( R = first[ v ] \)。 为方便处理，我们假设 \( L \le R \)，如果不满足则交换。 在 \( euler \) 序列的区间 \([ L, R ]\) 中，找到深度最小的节点，这个节点就是 \( u \) 和 \( v \) 的 LCA。 为什么？因为深度优先遍历的性质保证了：在 \( euler \) 序列中，\( u \) 和 \( v \) 的 LCA 一定出现在 \( u \) 和 \( v \) 的第一次出现位置之间，且它是这个区间内深度最小的节点（因为 LCA 深度最浅，且 DFS 一定会访问到它）。 步骤 3：用稀疏表处理 RMQ 稀疏表可以在 \( O(1) \) 时间内回答区间最小值查询，前提是进行 \( O(n \log n) \) 的预处理。 设 \( depth[ i] \) 是 \( euler[ i ] \) 对应节点的深度。 定义 \( st[ k][ i] \) 表示从 \( i \) 开始，长度为 \( 2^k \) 的区间中，深度最小值的 下标 。 预处理递推公式： 初始：\( st[ 0][ i ] = i \)（长度为1的区间，最小值就是自己） 递推：\( st[ k][ i] = \arg\min(depth[ st[ k-1][ i]], depth[ st[ k-1][ i+2^{k-1}] ]) \) 查询区间 \([ L, R ]\) 时： 设 \( k = \lfloor \log_ 2 (R - L + 1) \rfloor \) 比较区间 \([ L, L+2^k-1]\) 和 \([ R-2^k+1, R ]\) 这两个区间的最小值，取深度更小的那个下标即可。 步骤 4：查询 LCA 输入 \( u, v \)。 令 \( L = first[ u] \)，\( R = first[ v ] \)，如果 \( L > R \) 则交换。 在区间 \([ L, R ]\) 上查询深度最小的节点下标 \( idx \)。 答案就是 \( euler[ idx ] \)。 复杂度分析 预处理： DFS 遍历：\( O(n) \) 稀疏表构建：\( O(n \log n) \) 每次查询：\( O(1) \) 总复杂度：\( O(n \log n + m) \) 举例说明 还是上面的树，查询 LCA(4, 5)： \( first[ 4] = 2 \)，\( first[ 5] = 4 \)，区间为 [ 2, 4 ]。 \( euler[ 2..4] = [ 4, 2, 5] \)，对应的深度为 [ 2, 1, 2 ]。 深度最小的是深度为 1 的节点 \( euler[ 3 ] = 2 \)（注意下标 3 对应节点 2）。 所以 LCA(4, 5) = 2，正确。 查询 LCA(4, 3)： \( first[ 4] = 2 \)，\( first[ 3] = 7 \)，区间为 [ 2, 7 ]。 \( euler[ 2..7] = [ 4, 2, 5, 2, 1, 3] \)，深度为 [ 2, 1, 2, 1, 0, 1 ]。 深度最小的是深度为 0 的节点 \( euler[ 6 ] = 1 \)。 所以 LCA(4, 3) = 1，正确。 关键点 将 LCA 问题转化为 RMQ 问题的关键在于深度优先遍历序列和每个节点第一次出现位置的记录。 稀疏表是解决静态 RMQ 问题的高效数据结构，允许 \( O(1) \) 查询。 此方法适用于 静态树 （树的结构不会改变），预处理后可以高效回答大量查询。 这个解法是 LCA 问题的经典方法之一，在算法竞赛和实际应用中都非常高效。