最小公共祖先（LCA）问题的欧拉序列与RMQ解法
字数 2292 2025-12-07 22:37:14

最小公共祖先（LCA）问题的欧拉序列与RMQ解法

题目描述
给定一棵有根树（包含 n 个顶点）和若干查询，每个查询要求两个顶点的最小公共祖先（LCA），即同时是这两个顶点祖先的深度最大的顶点。要求设计一个算法，在 O(n log n) 的预处理时间和 O(1) 的查询时间内回答每个查询。

解题过程

1. 问题理解
最小公共祖先问题是树结构中的一个基本问题。朴素解法是：对于每个查询，分别从两个顶点向上跳至根，记录路径，然后比较路径找到最后一个公共顶点。但这样每个查询需要 O(n) 的时间。我们需要更高效的算法，利用欧拉序列将 LCA 问题转化为范围最小值查询（RMQ）问题，再通过稀疏表（Sparse Table）实现 O(1) 查询。

2. 核心思路

  • 对树进行深度优先遍历，记录每个顶点首次被访问时的时间戳，并生成一个欧拉序列（Euler Tour），即 DFS 遍历过程中访问到的所有顶点按顺序排列（每次进入和离开一个顶点时都记录它）。
  • 在欧拉序列中，任意两个顶点 u 和 v 的 LCA 就对应为它们在欧拉序列中第一次出现的位置之间的、深度最小的顶点。
  • 因此，LCA 问题转化为：在欧拉序列的一个区间内，找到深度最小的顶点。这是一个 RMQ 问题，可以用稀疏表在 O(1) 时间内回答。

3. 算法步骤

步骤 3.1：生成欧拉序列和相关数组

  • 执行 DFS 遍历树，从根节点开始。
  • 维护以下数组（假设顶点编号从 1 到 n）：
    • euler[]：欧拉序列，长度为 2n-1（因为 DFS 遍历每条边两次，顶点数 n 的树有 2n-1 个访问点）。
    • depth[]：与 euler[] 相同长度，记录欧拉序列每个位置对应顶点的深度（根深度为 0 或 1 均可，常用 0）。
    • firstOccurrence[]：长度为 n+1，记录每个顶点在 euler[] 中第一次出现的下标。
  • DFS 过程中，每当访问到一个顶点（包括首次进入和后续返回），就将其加入 euler[]，同时将其深度加入 depth[]，并记录第一次出现的位置。

示例
考虑一棵树：根为 1，连接 2 和 3，顶点 2 连接 4 和 5。
一个可能的欧拉序列（DFS 顺序：1 → 2 → 4 → 2 → 5 → 2 → 1 → 3 → 1）：
euler[] = [1, 2, 4, 2, 5, 2, 1, 3, 1]
depth[] = [0, 1, 2, 1, 2, 1, 0, 1, 0] （根深度 0）
firstOccurrence[]:
顶点 1 → 下标 0
顶点 2 → 下标 1
顶点 3 → 下标 7
顶点 4 → 下标 2
顶点 5 → 下标 4

步骤 3.2：构建稀疏表（Sparse Table）

  • 目标：对 depth[] 数组，能在 O(1) 时间内查询任意区间 [l, r] 中深度最小值的下标。
  • 预处理：
    • 设 m = 2n-1 为 depth[] 长度。
    • 构建二维数组 st[k][i]，表示从下标 i 开始、长度为 2^k 的区间中深度最小值的下标。
    • 递推公式：
      • 基础：st[0][i] = i（区间长度为 1，最小值下标就是自身）。
      • 递推：st[k][i] = argmin(depth[st[k-1][i]], depth[st[k-1][i + 2^{k-1}]])，即比较两个半区间的最小值下标，取深度更小的那个下标。
    • 预处理时间复杂度：O(m log m) = O(n log n)。
  • 查询区间 [l, r] 的最小值下标：
    • 设 k = floor(log2(r - l + 1))。
    • 区间 [l, r] 可以被两个长度为 2^k 的区间覆盖：[l, l+2^k-1] 和 [r-2^k+1, r]。
    • 比较 depth[st[k][l]] 和 depth[st[k][r-2^k+1]]，取深度更小的下标即可。
    • 查询时间 O(1)。

步骤 3.3：回答 LCA 查询
对于查询顶点 u 和 v：

  1. 在 euler[] 中找到它们第一次出现的位置：l = firstOccurrence[u], r = firstOccurrence[v]。
  2. 如果 l > r，交换它们，确保 l ≤ r。
  3. 在 depth[] 的区间 [l, r] 上查询深度最小值的下标 idx。
  4. LCA 就是 euler[idx]。
    因为欧拉序列中，u 和 v 之间的区间恰好包含了它们 LCA 在内的所有顶点，且 LCA 是该区间中深度最小的顶点。

4. 复杂度分析

  • 预处理：
    • DFS 生成数组：O(n)。
    • 构建稀疏表：O(n log n)。
  • 查询：每次 O(1)。
  • 空间：O(n log n) 用于稀疏表。

5. 关键点说明

  • 欧拉序列的长度为 2n-1，而非 n，因为每个顶点在 DFS 进出时都被记录。
  • 稀疏表查询 RMQ 要求可重复贡献（即区间重叠不影响最小值结果），深度数组满足此性质。
  • 此方法适用于静态树（树结构不变），若树动态变化，需用其他数据结构（如 Link-Cut Tree）。

6. 总结
通过欧拉序列将 LCA 转化为 RMQ，再利用稀疏表加速，是一种“预处理较重、查询极快”的典型策略，适合查询次数远大于 n 的场景。此算法是 LCA 问题的标准解法之一，与倍增法、Tarjan 离线算法并列常用。

最小公共祖先（LCA）问题的欧拉序列与RMQ解法 题目描述 给定一棵有根树（包含 n 个顶点）和若干查询，每个查询要求两个顶点的 最小公共祖先 （LCA），即同时是这两个顶点祖先的深度最大的顶点。要求设计一个算法，在 O(n log n) 的预处理时间和 O(1) 的查询时间内回答每个查询。 解题过程 1. 问题理解 最小公共祖先问题是树结构中的一个基本问题。朴素解法是：对于每个查询，分别从两个顶点向上跳至根，记录路径，然后比较路径找到最后一个公共顶点。但这样每个查询需要 O(n) 的时间。我们需要更高效的算法，利用 欧拉序列 将 LCA 问题转化为 范围最小值查询 （RMQ）问题，再通过稀疏表（Sparse Table）实现 O(1) 查询。 2. 核心思路 对树进行深度优先遍历，记录每个顶点 首次被访问时 的时间戳，并生成一个 欧拉序列 （Euler Tour），即 DFS 遍历过程中访问到的所有顶点按顺序排列（每次进入和离开一个顶点时都记录它）。 在欧拉序列中，任意两个顶点 u 和 v 的 LCA 就对应为它们在欧拉序列中 第一次出现的位置 之间的、 深度最小 的顶点。 因此，LCA 问题转化为：在欧拉序列的一个区间内，找到深度最小的顶点。这是一个 RMQ 问题，可以用稀疏表在 O(1) 时间内回答。 3. 算法步骤 步骤 3.1：生成欧拉序列和相关数组 执行 DFS 遍历树，从根节点开始。 维护以下数组（假设顶点编号从 1 到 n）： euler[] ：欧拉序列，长度为 2n-1（因为 DFS 遍历每条边两次，顶点数 n 的树有 2n-1 个访问点）。 depth[] ：与 euler[] 相同长度，记录欧拉序列每个位置对应顶点的深度（根深度为 0 或 1 均可，常用 0）。 firstOccurrence[] ：长度为 n+1，记录每个顶点在 euler[] 中 第一次出现 的下标。 DFS 过程中，每当 访问到一个顶点 （包括首次进入和后续返回），就将其加入 euler[] ，同时将其深度加入 depth[] ，并记录第一次出现的位置。 示例 考虑一棵树：根为 1，连接 2 和 3，顶点 2 连接 4 和 5。 一个可能的欧拉序列（DFS 顺序：1 → 2 → 4 → 2 → 5 → 2 → 1 → 3 → 1）： euler[] = [1, 2, 4, 2, 5, 2, 1, 3, 1] depth[] = [0, 1, 2, 1, 2, 1, 0, 1, 0] （根深度 0） firstOccurrence[]: 顶点 1 → 下标 0 顶点 2 → 下标 1 顶点 3 → 下标 7 顶点 4 → 下标 2 顶点 5 → 下标 4 步骤 3.2：构建稀疏表（Sparse Table） 目标：对 depth[] 数组，能在 O(1) 时间内查询任意区间 [l, r] 中深度最小值的 下标 。 预处理： 设 m = 2n-1 为 depth[] 长度。 构建二维数组 st[k][i] ，表示从下标 i 开始、长度为 2^k 的区间中深度最小值的下标。 递推公式： 基础： st[0][i] = i （区间长度为 1，最小值下标就是自身）。 递推： st[k][i] = argmin(depth[st[k-1][i]], depth[st[k-1][i + 2^{k-1}]]) ，即比较两个半区间的最小值下标，取深度更小的那个下标。 预处理时间复杂度：O(m log m) = O(n log n)。 查询区间 [l, r] 的最小值下标： 设 k = floor(log2(r - l + 1)) 。 区间 [l, r] 可以被两个长度为 2^k 的区间覆盖： [l, l+2^k-1] 和 [r-2^k+1, r] 。 比较 depth[st[k][l]] 和 depth[st[k][r-2^k+1]] ，取深度更小的下标即可。 查询时间 O(1)。 步骤 3.3：回答 LCA 查询 对于查询顶点 u 和 v： 在 euler[] 中找到它们第一次出现的位置： l = firstOccurrence[u] , r = firstOccurrence[v] 。 如果 l > r ，交换它们，确保 l ≤ r 。 在 depth[] 的区间 [l, r] 上查询深度最小值的下标 idx 。 LCA 就是 euler[idx] 。 因为欧拉序列中，u 和 v 之间的区间恰好包含了它们 LCA 在内的所有顶点，且 LCA 是该区间中深度最小的顶点。 4. 复杂度分析 预处理： DFS 生成数组：O(n)。 构建稀疏表：O(n log n)。 查询：每次 O(1)。 空间：O(n log n) 用于稀疏表。 5. 关键点说明 欧拉序列的长度为 2n-1，而非 n，因为每个顶点在 DFS 进出时都被记录。 稀疏表查询 RMQ 要求 可重复贡献 （即区间重叠不影响最小值结果），深度数组满足此性质。 此方法适用于静态树（树结构不变），若树动态变化，需用其他数据结构（如 Link-Cut Tree）。 6. 总结 通过欧拉序列将 LCA 转化为 RMQ，再利用稀疏表加速，是一种“预处理较重、查询极快”的典型策略，适合查询次数远大于 n 的场景。此算法是 LCA 问题的标准解法之一，与倍增法、Tarjan 离线算法并列常用。