xxx 最小公共祖先（LCA）问题的倍增算法
字数 2103 2025-11-07 12:33:00

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

题目描述：
给定一棵有根树（明确指定了根节点）和若干组查询，每组查询包含树中的两个节点。对于每一组查询，需要找出这两个节点的最小公共祖先（LCA）。最小公共祖先被定义为这两个节点的所有公共祖先中，深度最大的那个节点。

解题过程：

  1. 问题分析与预处理思路

    • 最直观的方法是，对于每个查询，将两个节点提升到同一深度，然后同时向上一步步移动，直到它们相遇。但在最坏情况下（例如树退化成一条链），单次查询的时间复杂度可能达到 O(n)，对于 Q 次查询，总复杂度为 O(Qn)，这在节点数 n 和查询次数 Q 都很大时效率较低。
    • 倍增算法的核心思想是通过预处理，为每个节点存储其向上跳跃 1, 2, 4, 8, ... 步所能到达的祖先节点。这样，在查询时，我们可以将节点的大幅度向上移动从“一步步”优化为“按2的幂次跳”，从而将单次查询的时间复杂度降低到 O(log n)。

  2. 算法详细步骤

    第一步：初始化与深度计算

    • 我们首先需要知道每个节点的深度（即节点到根节点的距离，根节点深度为0）。
    • 从根节点开始，进行一次深度优先搜索（DFS）或广度优先搜索（BFS），遍历整棵树。在遍历过程中，记录每个节点的深度 depth[u]。

    第二步：构建倍增表（预处理的核心）

    • 我们定义一个二维数组 parent（或常命名为 up, ancestor）。parent[u][k] 表示节点 u 向上跳跃 2^k 步后所到达的祖先节点。
    • 初始化 parent 表的第一层（k=0）：
      • 对于每个节点 u，parent[u][0] 就是 u 的直接父节点。根节点的 parent[root][0] 为 0 或 -1（表示没有祖先）。
    • 递推填充 parent 表的更高层（k=1, 2, ...）：
      • 递推公式为：parent[u][k] = parent[ parent[u][k-1] ][k-1]。
      • 这个公式的含义是：节点 u 向上跳 2^k 步，等价于先向上跳 2^(k-1) 步到达一个中间节点，再从那个中间节点向上跳 2^(k-1) 步。
      • 我们需要确定 k 的最大值。由于最多跳跃的步数不会超过树的深度，而树的深度最大为 n。因此，k 的最大值 max_k 只需满足 2^(max_k) >= n 即可，通常取 max_k = log2(n) + 1。

    第三步：处理查询
    对于每个查询 (节点 u, 节点 v)：

    • 1. 将两个节点提升到同一深度：
      • 假设 depth[u] > depth[v]，否则交换 u 和 v，确保 v 是深度较大的节点。
      • 计算深度差 d = depth[v] - depth[u]。
      • 将深度较大的节点 v 向上提升 d 步，使其与 u 处于同一深度。提升时，利用二进制思想：将深度差 d 看作一个二进制数。例如 d = 5（二进制 101），意味着需要跳 2^2 步和 2^0 步。我们从最大的幂次 max_k 开始尝试，如果 d 的当前二进制位为 1，则进行跳跃。
      • 具体操作：令 k 从 max_k 递减到 0。如果 depth[v] - (1 << k) >= depth[u]，说明跳 2^k 步不会超过 u 的深度，是安全的，那么我们就执行跳跃：v = parent[v][k]。
    • 2. 如果此时节点相同，则已找到LCA：
      • 如果提升后 u == v，说明原来的 u 就是 v 的祖先，LCA 就是 u。可以直接返回。
    • 3. 否则，同时向上跳跃直至其父节点相同：
      • 如果 u != v，说明它们在同一深度但不同节点。现在，我们让 u 和 v 同时向上跳跃，目标是跳到它们 LCA 的下一层（即直接子节点）。
      • 同样从最大的幂次 max_k 开始尝试。对于每个 k（从 max_k 递减到 0）：
        • 检查 parent[u][k] 是否等于 parent[v][k]。
        • 如果不相等，说明这个跳跃步长（2^k）是安全的，跳跃后还不会越过 LCA。那么我们就执行跳跃：u = parent[u][k] 和 v = parent[v][k]。
        • 如果相等，说明这个跳跃步长（2^k）太大了，会直接跳到 LCA 甚至更远，所以我们跳过这个 k，尝试更小的步长。
      • 这个循环结束后，u 和 v 将会位于 LCA 的下一层。此时，u 和 v 的直接父节点就是它们的 LCA。
    • 4. 返回结果：
      • LCA 就是 parent[u][0]（或 parent[v][0]，此时它们相等）。

总结：
倍增算法通过 O(n log n) 的预处理时间（构建 parent 表），将每个 LCA 查询的时间复杂度优化到了 O(log n)。这对于需要处理大量查询的场景非常高效。其核心在于利用二进制幂次的思想，将线性的跳跃过程转化为对数的跳跃次数。

xxx 最小公共祖先（LCA）问题的倍增算法 题目描述： 给定一棵有根树（明确指定了根节点）和若干组查询，每组查询包含树中的两个节点。对于每一组查询，需要找出这两个节点的最小公共祖先（LCA）。最小公共祖先被定义为这两个节点的所有公共祖先中，深度最大的那个节点。 解题过程： 问题分析与预处理思路 最直观的方法是，对于每个查询，将两个节点提升到同一深度，然后同时向上一步步移动，直到它们相遇。但在最坏情况下（例如树退化成一条链），单次查询的时间复杂度可能达到 O(n)，对于 Q 次查询，总复杂度为 O(Qn)，这在节点数 n 和查询次数 Q 都很大时效率较低。 倍增算法 的核心思想是通过预处理，为每个节点存储其向上跳跃 1, 2, 4, 8, ... 步所能到达的祖先节点。这样，在查询时，我们可以将节点的大幅度向上移动从“一步步”优化为“按2的幂次跳”，从而将单次查询的时间复杂度降低到 O(log n)。 算法详细步骤 第一步：初始化与深度计算 我们首先需要知道每个节点的深度（即节点到根节点的距离，根节点深度为0）。 从根节点开始，进行一次深度优先搜索（DFS）或广度优先搜索（BFS），遍历整棵树。在遍历过程中，记录每个节点的深度 depth[u] 。 第二步：构建倍增表（预处理的核心） 我们定义一个二维数组 parent （或常命名为 up , ancestor ）。 parent[u][k] 表示节点 u 向上跳跃 2^k 步后所到达的祖先节点。 初始化 parent 表的第一层（k=0）： 对于每个节点 u ， parent[u][0] 就是 u 的直接父节点。根节点的 parent[root][0] 为 0 或 -1（表示没有祖先）。 递推填充 parent 表的更高层（k=1, 2, ...）： 递推公式为： parent[u][k] = parent[ parent[u][k-1] ][k-1] 。 这个公式的含义是：节点 u 向上跳 2^k 步，等价于先向上跳 2^(k-1) 步到达一个中间节点，再从那个中间节点向上跳 2^(k-1) 步。 我们需要确定 k 的最大值。由于最多跳跃的步数不会超过树的深度，而树的深度最大为 n。因此，k 的最大值 max_k 只需满足 2^(max_ k) >= n 即可，通常取 max_k = log2(n) + 1 。 第三步：处理查询 对于每个查询 (节点 u , 节点 v )： 1. 将两个节点提升到同一深度： 假设 depth[u] > depth[v] ，否则交换 u 和 v ，确保 v 是深度较大的节点。 计算深度差 d = depth[v] - depth[u] 。 将深度较大的节点 v 向上提升 d 步，使其与 u 处于同一深度。提升时，利用二进制思想：将深度差 d 看作一个二进制数。例如 d = 5 （二进制 101），意味着需要跳 2^2 步和 2^0 步。我们从最大的幂次 max_k 开始尝试，如果 d 的当前二进制位为 1，则进行跳跃。 具体操作：令 k 从 max_k 递减到 0。如果 depth[v] - (1 << k) >= depth[u] ，说明跳 2^k 步不会超过 u 的深度，是安全的，那么我们就执行跳跃： v = parent[v][k] 。 2. 如果此时节点相同，则已找到LCA： 如果提升后 u == v ，说明原来的 u 就是 v 的祖先，LCA 就是 u 。可以直接返回。 3. 否则，同时向上跳跃直至其父节点相同： 如果 u != v ，说明它们在同一深度但不同节点。现在，我们让 u 和 v 同时向上跳跃，目标是跳到它们 LCA 的下一层（即直接子节点）。 同样从最大的幂次 max_k 开始尝试。对于每个 k （从 max_k 递减到 0）： 检查 parent[u][k] 是否等于 parent[v][k] 。 如果 不相等 ，说明这个跳跃步长（2^k）是安全的，跳跃后还不会越过 LCA。那么我们就执行跳跃： u = parent[u][k] 和 v = parent[v][k] 。 如果相等，说明这个跳跃步长（2^k）太大了，会直接跳到 LCA 甚至更远，所以我们跳过这个 k ，尝试更小的步长。 这个循环结束后， u 和 v 将会位于 LCA 的下一层。此时， u 和 v 的直接父节点就是它们的 LCA。 4. 返回结果： LCA 就是 parent[u][0] （或 parent[v][0] ，此时它们相等）。 总结： 倍增算法通过 O(n log n) 的预处理时间（构建 parent 表），将每个 LCA 查询的时间复杂度优化到了 O(log n)。这对于需要处理大量查询的场景非常高效。其核心在于利用二进制幂次的思想，将线性的跳跃过程转化为对数的跳跃次数。