最小公共祖先（Lowest Common Ancestor, LCA）的稀疏表（Sparse Table）算法
字数 2817 2025-12-18 01:21:19

最小公共祖先（Lowest Common Ancestor, LCA）的稀疏表（Sparse Table）算法

题目描述
给定一棵有 \(n\) 个节点的树（无向、连通、无环），以及 \(m\) 次查询。每次查询给出两个节点 \(u\) 和 \(v\)，要求快速回答它们的最小公共祖先（LCA）。最小公共祖先是指深度最大的、同时是 \(u\) 和 \(v\) 祖先的节点。你的目标是在 \(O(n \log n)\) 预处理时间和 \(O(1)\) 每次查询时间内回答所有查询。

解题过程循序渐进讲解
这个问题是图论（特别是树结构）中的经典查询问题。为了达到 \(O(1)\) 查询，我们需要利用欧拉序列和范围最小值查询（RMQ）的技术。下面我们一步步拆解。

第一步：理解核心思路
如果我们能快速得到树上任意两点的 LCA，就能支持许多树上的操作。朴素方法是沿着父指针向上爬，但最坏需要 \(O(n)\) 时间。我们的目标是将 LCA 问题转化为另一个问题：在序列上查询区间最小值（RMQ）。步骤是：

  1. 对树进行深度优先遍历（DFS），生成欧拉序列（Euler Tour）和深度序列。
  2. 在欧拉序列中，任意两点的 LCA 对应它们在序列中首次出现的位置之间的、深度最小的节点。
  3. 通过稀疏表（Sparse Table）预计算所有可能的区间最小值查询，就能在 \(O(1)\) 时间回答 RMQ，从而得到 LCA。

第二步：生成欧拉序列和深度序列
我们执行一次 DFS，从根节点（假设为节点 0）开始，记录：

  • 欧拉序列 \(E[0..2n-2]\)：每次访问一个节点（包括进入和回溯返回时）就将其加入序列。这样每个节点会出现多次。
  • 深度序列 \(D[0..2n-2]\)：与 \(E\) 对应，记录每个位置节点的深度。
  • 首次出现位置 \(first[u]\)：节点 \(u\) 在欧拉序列中第一次出现的下标。

例如，对于树：0-1, 0-2, 1-3, 1-4（根为0），一种可能的 DFS 遍历得到的欧拉序列和深度序列如下：
节点访问顺序：0 -> 1 -> 3 -> 1 -> 4 -> 1 -> 0 -> 2 -> 0
对应 \(E\) = [0, 1, 3, 1, 4, 1, 0, 2, 0]
对应 \(D\) = [0, 1, 2, 1, 2, 1, 0, 1, 0]
首次出现：first[0]=0, first[1]=1, first[2]=7, first[3]=2, first[4]=4

关键性质：对于查询 LCA(u, v)，设 \(l = first[u]\), \(r = first[v]\)，并假设 \(l \le r\)（否则交换）。在 \(D[l..r]\) 中，深度最小的位置对应的节点就是 LCA(u, v)。这是因为在欧拉序列中，\(u\) 和 \(v\) 之间的部分对应了从 \(u\) 走到 \(v\) 的路径（经过 LCA），而 LCA 是深度最小的节点。

第三步：用稀疏表解决 RMQ
现在问题转化为：给定数组 \(D[0..M-1]\)（这里 \(M = 2n-1\)），需要快速查询任意区间 \([l, r]\) 的最小值的位置（下标）。稀疏表（Sparse Table）能在 \(O(M \log M)\) 预处理、\(O(1)\) 查询内完成。

预处理：
定义 \(st[i][k]\) 表示从下标 \(i\) 开始、长度为 \(2^k\) 的区间中，深度最小值的下标（注意不是最小值本身，而是下标，因为我们需要知道对应哪个节点）。
转移方程：

\[st[i][k] = \begin{cases} i & \text{if } k = 0 \\ \arg\min(D[st[i][k-1]], D[st[i+2^{k-1}][k-1]]) & \text{if } k > 0 \end{cases} \]

其中 \(\arg\min\) 表示取深度更小的那个下标（如果深度相同，任取一个，比如取更小的下标，不影响 LCA 结果）。
计算顺序：从小到大枚举 \(k\)，直到 \(2^k > M\)。

查询 RMQ(l, r)：
设 \(len = r - l + 1\)，计算 \(k = \lfloor \log_2(len) \rfloor\)。
那么区间 \([l, r]\) 可以拆成两个长度为 \(2^k\) 的区间：\([l, l+2^k-1]\) 和 \([r-2^k+1, r]\)，它们覆盖了整个 \([l, r]\)。
取 \(st[l][k]\) 和 \(st[r-2^k+1][k]\) 中深度更小的下标作为答案。

第四步：整合为 LCA 查询

  1. 输入节点 \(u, v\)。
  2. 设 \(l = first[u]\), \(r = first[v]\)，如果 \(l > r\) 则交换。
  3. 在深度序列 \(D\) 上查询区间 \([l, r]\) 的最小值位置 \(p\)（用稀疏表 RMQ）。
  4. 答案 LCA(u, v) = \(E[p]\)。

第五步：复杂度分析

  • 生成欧拉序列和深度序列：一次 DFS，\(O(n)\) 时间。
  • 稀疏表预处理：\(O(M \log M) = O(n \log n)\)，因为 \(M = 2n-1\)。
  • 每次查询：两次查表、比较，\(O(1)\)。
  • 空间：稀疏表 \(O(n \log n)\)，其他数组 \(O(n)\)。

第六步：示例
沿用上面的树，查询 LCA(3, 4)：
first[3]=2, first[4]=4, 区间 D[2..4] = [2, 1, 2]，最小值下标 p=3（深度1），E[3]=1，所以 LCA(3,4)=1。正确。

查询 LCA(3, 2)：
first[3]=2, first[2]=7, 区间 D[2..7] = [2, 1, 2, 1, 0, 1]，最小值下标 p=6（深度0），E[6]=0，所以 LCA(3,2)=0。正确。

总结
这种方法将 LCA 转化为 RMQ，并利用稀疏表实现常数查询，是一种高效的在线算法。注意稀疏表不支持动态更新（静态树），如果树会变，需要用其他数据结构如树链剖分或 Link-Cut Tree。但在静态树上，这是最常用的 \(O(1)\) 查询 LCA 方法之一。

最小公共祖先（Lowest Common Ancestor, LCA）的稀疏表（Sparse Table）算法 题目描述 给定一棵有 \( n \) 个节点的树（无向、连通、无环），以及 \( m \) 次查询。每次查询给出两个节点 \( u \) 和 \( v \)，要求快速回答它们的最小公共祖先（LCA）。最小公共祖先是指深度最大的、同时是 \( u \) 和 \( v \) 祖先的节点。你的目标是在 \( O(n \log n) \) 预处理时间和 \( O(1) \) 每次查询时间内回答所有查询。 解题过程循序渐进讲解 这个问题是图论（特别是树结构）中的经典查询问题。为了达到 \( O(1) \) 查询，我们需要利用 欧拉序列 和 范围最小值查询 （RMQ）的技术。下面我们一步步拆解。 第一步：理解核心思路 如果我们能快速得到树上任意两点的 LCA，就能支持许多树上的操作。朴素方法是沿着父指针向上爬，但最坏需要 \( O(n) \) 时间。我们的目标是将 LCA 问题转化为另一个问题：在序列上查询区间最小值（RMQ）。步骤是： 对树进行深度优先遍历（DFS），生成欧拉序列（Euler Tour）和深度序列。 在欧拉序列中，任意两点的 LCA 对应它们在序列中首次出现的位置之间的、深度最小的节点。 通过稀疏表（Sparse Table）预计算所有可能的区间最小值查询，就能在 \( O(1) \) 时间回答 RMQ，从而得到 LCA。 第二步：生成欧拉序列和深度序列 我们执行一次 DFS，从根节点（假设为节点 0）开始，记录： 欧拉序列 \( E[ 0..2n-2 ] \)：每次访问一个节点（包括进入和回溯返回时）就将其加入序列。这样每个节点会出现多次。 深度序列 \( D[ 0..2n-2 ] \)：与 \( E \) 对应，记录每个位置节点的深度。 首次出现位置 \( first[ u ] \)：节点 \( u \) 在欧拉序列中第一次出现的下标。 例如，对于树：0-1, 0-2, 1-3, 1-4（根为0），一种可能的 DFS 遍历得到的欧拉序列和深度序列如下： 节点访问顺序：0 -> 1 -> 3 -> 1 -> 4 -> 1 -> 0 -> 2 -> 0 对应 \( E \) = [ 0, 1, 3, 1, 4, 1, 0, 2, 0 ] 对应 \( D \) = [ 0, 1, 2, 1, 2, 1, 0, 1, 0 ] 首次出现：first[ 0]=0, first[ 1]=1, first[ 2]=7, first[ 3]=2, first[ 4 ]=4 关键性质：对于查询 LCA(u, v)，设 \( l = first[ u] \), \( r = first[ v] \)，并假设 \( l \le r \)（否则交换）。在 \( D[ l..r ] \) 中，深度最小的位置对应的节点就是 LCA(u, v)。这是因为在欧拉序列中，\( u \) 和 \( v \) 之间的部分对应了从 \( u \) 走到 \( v \) 的路径（经过 LCA），而 LCA 是深度最小的节点。 第三步：用稀疏表解决 RMQ 现在问题转化为：给定数组 \( D[ 0..M-1] \)（这里 \( M = 2n-1 \)），需要快速查询任意区间 \([ l, r ]\) 的最小值的位置（下标）。稀疏表（Sparse Table）能在 \( O(M \log M) \) 预处理、\( O(1) \) 查询内完成。 预处理： 定义 \( st[ i][ k] \) 表示从下标 \( i \) 开始、长度为 \( 2^k \) 的区间中，深度最小值的 下标 （注意不是最小值本身，而是下标，因为我们需要知道对应哪个节点）。 转移方程： \[ st[ i][ k ] = \begin{cases} i & \text{if } k = 0 \\ \arg\min(D[ st[ i][ k-1]], D[ st[ i+2^{k-1}][ k-1] ]) & \text{if } k > 0 \end{cases} \] 其中 \(\arg\min\) 表示取深度更小的那个下标（如果深度相同，任取一个，比如取更小的下标，不影响 LCA 结果）。 计算顺序：从小到大枚举 \( k \)，直到 \( 2^k > M \)。 查询 RMQ(l, r)： 设 \( len = r - l + 1 \)，计算 \( k = \lfloor \log_ 2(len) \rfloor \)。 那么区间 \([ l, r]\) 可以拆成两个长度为 \( 2^k \) 的区间：\([ l, l+2^k-1]\) 和 \([ r-2^k+1, r]\)，它们覆盖了整个 \([ l, r ]\)。 取 \( st[ l][ k] \) 和 \( st[ r-2^k+1][ k ] \) 中深度更小的下标作为答案。 第四步：整合为 LCA 查询 输入节点 \( u, v \)。 设 \( l = first[ u] \), \( r = first[ v ] \)，如果 \( l > r \) 则交换。 在深度序列 \( D \) 上查询区间 \([ l, r ]\) 的最小值位置 \( p \)（用稀疏表 RMQ）。 答案 LCA(u, v) = \( E[ p ] \)。 第五步：复杂度分析 生成欧拉序列和深度序列：一次 DFS，\( O(n) \) 时间。 稀疏表预处理：\( O(M \log M) = O(n \log n) \)，因为 \( M = 2n-1 \)。 每次查询：两次查表、比较，\( O(1) \)。 空间：稀疏表 \( O(n \log n) \)，其他数组 \( O(n) \)。 第六步：示例 沿用上面的树，查询 LCA(3, 4)： first[ 3]=2, first[ 4]=4, 区间 D[ 2..4] = [ 2, 1, 2]，最小值下标 p=3（深度1），E[ 3 ]=1，所以 LCA(3,4)=1。正确。 查询 LCA(3, 2)： first[ 3]=2, first[ 2]=7, 区间 D[ 2..7] = [ 2, 1, 2, 1, 0, 1]，最小值下标 p=6（深度0），E[ 6 ]=0，所以 LCA(3,2)=0。正确。 总结 这种方法将 LCA 转化为 RMQ，并利用稀疏表实现常数查询，是一种高效的在线算法。注意稀疏表不支持动态更新（静态树），如果树会变，需要用其他数据结构如树链剖分或 Link-Cut Tree。但在静态树上，这是最常用的 \( O(1) \) 查询 LCA 方法之一。