RMQ 与 LCA 的等价归约

Euler walk 把树上两点之间必须回到共同祖先的过程画成深度曲线，最低点就是 LCA；反向的笛卡尔树又把数组最小值变成覆盖区间两端的最低祖先。两条线性归约保留查询接口，使任一方向的最优结构都能转移到另一问题。

图中把深度位置2至5写成闭区间 $[2,5]$；调用本页采用的半开 RMQ 接口时，应写作 ${\mathrm{RMQ}}_D(2,6)$，返回位置4，再由 $E[4]=r$ 还原祖先。

小树图像与约定 ​

根 $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 数组在首次写入后不再覆盖；查询先取两次首次位置的最小、最大值，再把右端加一，才能交给半开 RMQ。

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)$，等价性本身不会自动带来线性空间。