RMQ 与 LCA 的等价归约

LCA 到 ±1 RMQ ​

对根树做完整树上 Euler 序公理库树的 Euler Tour 技巧Euler tour technique for trees用 DFS 次序把子树或树上行走线性化，并区分三种常见序列。：进入或返回一个顶点都记录该顶点与深度，得到顶点序列 $E$ 和深度数组 $D$，相邻深度恰差 $\pm 1$。令 first$(v)$ 为 $v$ 首次出现位置，则

$$\mathrm{LCA}(u,v)=E[\arg \underset{i\in [first(u),first(v)]}{min}D[i]].$$

因为从 $u$ 的首次位置走到 $v$ 的首次位置，tour 必须先回升到两者最低公共祖先，且区间内不会到更浅的祖先。构造长度 $2n-1$，故预处理和空间线性。

RMQ 到 LCA ​

给数组 $A$，构造稳定 tie-breaking 的最小 Cartesian tree：中序次序等于数组下标，父键不大于子键。任意 $l\le r$，

$${\mathrm{RMQ}}_A(l,r)={\mathrm{LCA}}_{CT(A)}(l,r).$$

区间最小位置必须是端点在 Cartesian tree 中的最低共同祖先；否则中序区间或堆序会矛盾。Cartesian tree 可用单调栈在线性时间构造。

小树图像与约定 ​

根 $r$ 有孩子 $a,b$，$a$ 又有孩子 $c$。完整 tour 是 $r,a,c,a,r,b,r$，深度为 $0,1,2,1,0,1,0$；$c$ 与 $b$ 首次位置之间的最小深度在 $r$，所以 LCA 为 $r$。若随意选“最后出现”却仍套首次位置证明，区间可能改变。

边界与消歧 ​

两问题不是定义相同，而是在静态模型中线性互归约。LCA 方向产生特殊的 ±1 RMQ，Four Russians 可利用这一点；反方向则用一般数组的 Cartesian tree。重复最小值必须固定选最左或最右，且全链保持一致。点更新会改变 Cartesian tree，静态等价不直接给动态 $O(1)$ 查询。

线性构建细节 ​

Euler tour 必须记录每次沿边下行和返回，若只记录 preorder，两个节点首次出现区间的最低深度未必经过 LCA。first 数组在首次写入后不再覆盖；查询若 $first(u)>first(v)$ 先交换端点。

Cartesian tree 用单调递增栈扫描数组：弹出所有比当前值大的位置，最后弹出者成为当前左子，当前成为栈顶右子。每位置进出栈一次，构建 $O(n)$；相等值是否弹出决定最左/最右最小 tie-breaking。

端点与重复最小值 ​

设 Euler 深度片段为 $[2,1,2,1,2]$，区间内最小深度 1 出现两次。任取其一都映到同一个 LCA 时结论不受影响，但从一般数组构造 Cartesian tree 时，必须固定“相等取左”或“相等取右”，并在 RMQ 与 LCA 两端使用同一规则，否则重复最小值会选到不同节点。

归约的成本也要分开记：Euler 序把 $n$ 节点树变为长度 $2n-1$ 的 $\pm 1$ 数组；若使用 Four Russians 的 $\pm 1$ RMQ，可在线性预处理、$O(1)$ 查询。只套普通 sparse table 则预处理和空间为 $O(n\log n)$，等价性本身不会自动带来线性空间。

参考资料

• Michael Bender, Martin Farach-Colton, The LCA Problem Revisited, LATIN, 2000.
• Dov Harel, Robert Tarjan, Fast Algorithms for Finding Nearest Common Ancestors, SIAM J. Comput., 1984.