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

字数 2370 2025-12-10 08:48:53

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

题目描述
给定一棵有 \(n\) 个节点的有根树，以及 \(m\) 次查询，每次查询指定两个节点 \(u\) 和 \(v\)，要求找到它们的最近公共祖先（Lowest Common Ancestor, LCA），即深度最大的、同时是 \(u\) 和 \(v\) 祖先的节点。树以根节点已知的方式给出（通常根为 1 号节点）。目标是高效回答所有查询，其中 \(n, m\) 可能达到 \(10^5\) 甚至更大。

解题过程

1. 问题理解与基础思路

最近公共祖先的定义：在树中，节点 \(a\) 是节点 \(b\) 的祖先，当且仅当 \(a\) 在从根到 \(b\) 的路径上。\(u\) 和 \(v\) 的 LCA 是深度最大（离根最远）的公共祖先。
朴素解法：从 \(u\) 和 \(v\) 分别向上跳至根，记录路径上的所有祖先，然后比较找到最深的公共节点。单次查询时间复杂度为 \(O(h)\)，其中 \(h\) 是树高，最坏情况 \(h = O(n)\)，总复杂度 \(O(nm)\) 不可接受。
目标：利用预处理，将单次查询优化到 \(O(\log n)\)。

2. 倍增算法的核心思想

预处理每个节点向上 \(2^k\) 步所能到达的祖先节点，存储在一个二维数组 up[u][k] 中，表示节点 \(u\) 向上跳 \(2^k\) 步后到达的节点（若跳出根则记为 0 或 -1）。
利用二进制拆分思想：任意整数（跳跃步数）可表示为若干 2 的幂次之和，因此从节点向上跳任意步可转化为多次跳 2 的幂次。

3. 算法步骤详解

步骤 1：预处理深度与父亲节点

进行一次 DFS 或 BFS，从根节点开始，计算每个节点的深度 depth[u] 和直接父亲 parent[u]（即向上 1 步的节点）。
同时可初始化 up[u][0] = parent[u]。

步骤 2：预处理倍增表

设最大幂次 \(K = \lfloor \log_2 n \rfloor\)（因为最多跳 \(n-1\) 步）。
递推计算：

\[ \text{up}[u][k] = \text{up}[\ \text{up}[u][k-1]\ ][k-1], \quad k = 1, 2, \dots, K \]

含义：从 \(u\) 向上跳 \(2^k\) 步，等价于先跳 \(2^{k-1}\) 步，再从那里跳 \(2^{k-1}\) 步。

时间复杂度：\(O(n \log n)\)。

步骤 3：单次查询 LCA(u, v)

输入两个节点 \(u, v\)。
情况 1：如果 \(u = v\)，则 LCA 就是 \(u\)。
情况 2：确保 \(u\) 是较深的节点（若 depth[u] < depth[v]，则交换 \(u, v\)）。
调整深度：将 \(u\) 向上跳，直到与 \(v\) 同深度。
方法：从大到小枚举 \(k\)（从 \(K\) 到 0），若 depth[up[u][k]] >= depth[v]，则令 u = up[u][k]。这利用了二进制拆分，例如深度差为 5（二进制 101），则依次跳 \(2^2\) 和 \(2^0\) 步。
特判：若此时 \(u = v\)，则 LCA 为 \(v\)（即 \(v\) 是 \(u\) 的祖先）。
同时上跳：从大到小枚举 \(k\)，若 up[u][k] != up[v][k]，则令 u = up[u][k], v = up[v][k]。这会使 \(u, v\) 跳到 LCA 的直接子节点。
最终 LCA 为 up[u][0]（即 \(u\) 的父亲）。

4. 复杂度分析

预处理：\(O(n \log n)\) 时间，\(O(n \log n)\) 空间存储倍增表。
单次查询：\(O(\log n)\)。
总复杂度：\(O((n + m) \log n)\)，适合大规模查询。

5. 举例说明
假设树如下（根为 1）：

查询 LCA(4, 5)。

预处理得到 depth: d[1]=0, d[2]=1, d[3]=1, d[4]=2, d[5]=2。up 表略。
查询：u=4, v=5，depth[4]=depth[5]，无需调整深度。
同时上跳：K=2（因 n=5）。k=2: up[4][2]=0, up[5][2]=0，相等，不跳。k=1: up[4][1]=1, up[5][1]=1，相等，不跳。k=0: up[4][0]=2, up[5][0]=2，相等，不跳。此时 u=4, v=5。
注意：由于 u≠v，但 up[u][0]=up[v][0]=2，所以 LCA=2。
（注：实际实现中，若 up[u][k] != up[v][k] 才跳，否则不跳；最后返回 up[u][0]。）

6. 常见优化与变体

可结合 DFS 记录进入/离开时间，用于快速判断祖先关系（但倍增本身已足够高效）。
倍增思想还可用于查询路径上的第 k 个祖先、路径最大值等问题。

总结
倍增算法通过二进制拆分，将树上跳跃转化为若干次 2 的幂次跳跃，实现了 LCA 查询的快速响应。其思想是典型的“以空间换时间”，预处理后支持高效在线查询，是解决 LCA 问题的经典方法之一。

寻找最小公共祖先（LCA）问题的倍增算法题目描述给定一棵有 \( n \) 个节点的有根树，以及 \( m \) 次查询，每次查询指定两个节点 \( u \) 和 \( v \)，要求找到它们的最近公共祖先（Lowest Common Ancestor, LCA），即深度最大的、同时是 \( u \) 和 \( v \) 祖先的节点。树以根节点已知的方式给出（通常根为 1 号节点）。目标是高效回答所有查询，其中 \( n, m \) 可能达到 \( 10^5 \) 甚至更大。解题过程 1. 问题理解与基础思路最近公共祖先的定义：在树中，节点 \( a \) 是节点 \( b \) 的祖先，当且仅当 \( a \) 在从根到 \( b \) 的路径上。\( u \) 和 \( v \) 的 LCA 是深度最大（离根最远）的公共祖先。朴素解法：从 \( u \) 和 \( v \) 分别向上跳至根，记录路径上的所有祖先，然后比较找到最深的公共节点。单次查询时间复杂度为 \( O(h) \)，其中 \( h \) 是树高，最坏情况 \( h = O(n) \)，总复杂度 \( O(nm) \) 不可接受。目标：利用预处理，将单次查询优化到 \( O(\log n) \)。 2. 倍增算法的核心思想预处理每个节点向上 \( 2^k \) 步所能到达的祖先节点，存储在一个二维数组 up[u][k] 中，表示节点 \( u \) 向上跳 \( 2^k \) 步后到达的节点（若跳出根则记为 0 或 -1）。利用二进制拆分思想：任意整数（跳跃步数）可表示为若干 2 的幂次之和，因此从节点向上跳任意步可转化为多次跳 2 的幂次。 3. 算法步骤详解步骤 1：预处理深度与父亲节点进行一次 DFS 或 BFS，从根节点开始，计算每个节点的深度 depth[u] 和直接父亲 parent[u] （即向上 1 步的节点）。同时可初始化 up[u][0] = parent[u] 。步骤 2：预处理倍增表设最大幂次 \( K = \lfloor \log_ 2 n \rfloor \)（因为最多跳 \( n-1 \) 步）。递推计算： \[ \text{up}[ u][ k] = \text{up}[ \ \text{up}[ u][ k-1]\ ][ k-1 ], \quad k = 1, 2, \dots, K \] 含义：从 \( u \) 向上跳 \( 2^k \) 步，等价于先跳 \( 2^{k-1} \) 步，再从那里跳 \( 2^{k-1} \) 步。时间复杂度：\( O(n \log n) \)。步骤 3：单次查询 LCA(u, v) 输入两个节点 \( u, v \)。情况 1 ：如果 \( u = v \)，则 LCA 就是 \( u \)。情况 2 ：确保 \( u \) 是较深的节点（若 depth[u] < depth[v] ，则交换 \( u, v \)）。调整深度：将 \( u \) 向上跳，直到与 \( v \) 同深度。方法：从大到小枚举 \( k \)（从 \( K \) 到 0），若 depth[up[u][k]] >= depth[v] ，则令 u = up[u][k] 。这利用了二进制拆分，例如深度差为 5（二进制 101），则依次跳 \( 2^2 \) 和 \( 2^0 \) 步。特判：若此时 \( u = v \)，则 LCA 为 \( v \)（即 \( v \) 是 \( u \) 的祖先）。同时上跳：从大到小枚举 \( k \)，若 up[u][k] != up[v][k] ，则令 u = up[u][k] , v = up[v][k] 。这会使 \( u, v \) 跳到 LCA 的直接子节点。最终 LCA 为 up[u][0] （即 \( u \) 的父亲）。 4. 复杂度分析预处理：\( O(n \log n) \) 时间，\( O(n \log n) \) 空间存储倍增表。单次查询：\( O(\log n) \)。总复杂度：\( O((n + m) \log n) \)，适合大规模查询。 5. 举例说明假设树如下（根为 1）：查询 LCA(4, 5)。预处理得到 depth : d[ 1]=0, d[ 2]=1, d[ 3]=1, d[ 4]=2, d[ 5]=2。 up 表略。查询：u=4, v=5，depth[ 4]=depth[ 5 ]，无需调整深度。同时上跳：K=2（因 n=5）。k=2: up[ 4][ 2]=0, up[ 5][ 2]=0，相等，不跳。k=1: up[ 4][ 1]=1, up[ 5][ 1]=1，相等，不跳。k=0: up[ 4][ 0]=2, up[ 5][ 0 ]=2，相等，不跳。此时 u=4, v=5。注意：由于 u≠v，但 up[ u][ 0]=up[ v][ 0 ]=2，所以 LCA=2。（注：实际实现中，若 up[ u][ k] != up[ v][ k] 才跳，否则不跳；最后返回 up[ u][ 0 ]。） 6. 常见优化与变体可结合 DFS 记录进入/离开时间，用于快速判断祖先关系（但倍增本身已足够高效）。倍增思想还可用于查询路径上的第 k 个祖先、路径最大值等问题。总结倍增算法通过二进制拆分，将树上跳跃转化为若干次 2 的幂次跳跃，实现了 LCA 查询的快速响应。其思想是典型的“以空间换时间”，预处理后支持高效在线查询，是解决 LCA 问题的经典方法之一。