最小公共祖先（LCA）问题的 RMQ 解法
题目描述
给定一棵有根树（包含 n 个节点，节点编号通常为 0 到 n-1 或 1 到 n），并处理多组查询。每个查询给出两个节点 u 和 v，要求求出它们在这棵树中的最小公共祖先（Lowest Common Ancestor, LCA），即深度最大的、同时是 u 和 v 的祖先的节点。
例如，在下面的树中（根为 0）：
0
/ \
1 2
/ \
3 4
查询 LCA(3,4) 的答案是 1，LCA(3,2) 的答案是 0。
目标：实现一个能快速预处理，并能在 O(1) 时间内回答每个查询的算法。
解题过程
1. 核心思路
LCA 问题可以通过欧拉序列（Euler Tour）将问题转化为区间最小值查询（Range Minimum Query, RMQ）问题，然后利用 RMQ 的 Sparse Table 数据结构在 O(1) 时间内回答每个查询。
整体步骤：
- 对树进行深度优先搜索（DFS），生成欧拉序列和深度序列。
- 记录每个节点在欧拉序列中首次出现的位置。
- 对于查询 LCA(u, v)，找到它们在欧拉序列中首次出现的位置构成的区间，查询该区间内深度最小的节点，即为 LCA。
2. 生成欧拉序列与深度序列
- 欧拉序列（Euler Tour Sequence）：在 DFS 遍历树时，每次“进入”一个节点，就把该节点加入序列；回溯离开时，也把该节点加入序列。
这样，树中每条边会被走过两次，序列长度为 2n-1（假设树有 n 个节点）。 - 深度序列（Depth Sequence）：与欧拉序列同步记录，存储欧拉序列中每个节点对应的深度。
- 首次出现位置数组（First Occurrence Array）：记录每个节点在欧拉序列中第一次出现的位置索引。
举例：上面的树（根 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]
首次出现位置 F = [0, 1, 7, 2, 4] （节点 0 第一次出现在 E[0]，节点 1 在 E[1]，节点 2 在 E[7]，…）
3. 转化为 RMQ 问题
对于查询 LCA(u, v)：
- 从 F 数组得到 u 和 v 在欧拉序列中第一次出现的位置：
pos_u = F[u]，pos_v = F[v]。 - 假设
pos_u < pos_v，则在欧拉序列的区间[pos_u, pos_v]中，深度最小的那个节点就是 u 和 v 的 LCA。
原因：欧拉序列中，任意两个节点第一次出现位置之间的子序列，必然包含了它们 LCA 的出现（且 LCA 在该区间内的深度是最小的，因为 LCA 是它们最近的公共祖先，深度比其它祖先更小）。 - 问题转化为：在深度序列 D 的区间
[pos_u, pos_v]中，找到最小值对应的节点（注意是节点编号，不是深度值）。
4. 用 Sparse Table 解决 RMQ
RMQ 问题：给定一个静态数组，多次查询任意区间的最小值（及下标）。Sparse Table 可以在 O(n log n) 预处理后，O(1) 回答查询。
Sparse Table 构建：
- 设
st[i][j]表示从 D 数组的索引 i 开始，长度为 2^j 的区间内，最小深度值对应的节点在欧拉序列中的索引（为了得到节点编号，我们通常存储索引，然后通过欧拉序列得到节点）。 - 递推关系：
- 当 j=0：
st[i][0] = i（区间长度为 1，最小值就是 i 本身）。 - 当 j>0：
st[i][j] = argmin(D[st[i][j-1]], D[st[i+2^(j-1)][j-1]])，即比较前后两半的最小值，取深度更小的那个索引。
- 当 j=0：
- 预处理时间复杂度 O(n log n)。
RMQ 查询：
- 对于区间 [l, r]，令 k = floor(log2(r - l + 1))。
- 比较两个长度为 2^k 的区间：
- 区间1：[l, l+2^k-1]，对应
st[l][k] - 区间2：[r-2^k+1, r]，对应
st[r-2^k+1][k]
- 区间1：[l, l+2^k-1]，对应
- 取这两个区间中深度更小的那个索引作为答案 idx。
- 最终 LCA = E[idx]。
5. 算法步骤总结
- 预处理：
- 进行一次 DFS，得到欧拉序列 E、深度序列 D、首次出现位置 F。
- 构建 D 序列的 Sparse Table（存储索引，比较时用 D 数组的值）。
- 查询 LCA(u, v)：
- 令
l = F[u],r = F[v]，如果 l > r 则交换。 - 在 D 序列的区间 [l, r] 上做 RMQ，得到最小深度对应的索引 idx。
- 返回 E[idx] 作为 LCA。
- 令
6. 复杂度分析
- 预处理：DFS O(n)，Sparse Table 构建 O(n log n)。
- 查询：O(1)。
- 空间：O(n log n) 存储 Sparse Table。
举例验证
对前面的树：
E = [0,1,3,1,4,1,0,2,0]
D = [0,1,2,1,2,1,0,1,0]
F = [0,1,7,2,4]
查询 LCA(3,4)：
- l=F[3]=2, r=F[4]=4。
- 在 D[2..4] = [2,1,2] 中，最小值 1 的索引是 3。
- E[3]=1，所以 LCA=1 ✅
查询 LCA(3,2)：
- l=F[3]=2, r=F[2]=7。
- 在 D[2..7] = [2,1,2,1,0,1] 中，最小值 0 的索引是 6。
- E[6]=0，所以 LCA=0 ✅