11 篇让更新和区间查询都保持对数成本。如果数组从建立后就不再改变，可以保存更多重叠区间的答案，换取常数次合并的查询。Sparse Table适合这种静态场景，但它的常数查询公式并不适用于所有聚合运算。

本篇先实现静态区间最小值位置查询，再用一次树遍历把最近公共祖先LCA转换成它。输入分别是不可更新的数组和合法有根树；不能把“已有预处理”当成数据修改后答案仍有效的理由。

两块为什么覆盖整个区间

数组长n，argmin(l,r)返回非空半开区间内最小值最靠左的位置，要求0≤l<r≤n。空数组可建立对象，但没有合法查询；越界或空查询抛IndexError。把每个元素表示成 (value,index)，按字典序取min，就能同时处理最小值和并列位置。

ST[k][i]保存从i开始、长2^k的完整区间答案。0层就是单元素；更高层由相邻两半合并：

ST[k][i]=min⁡(ST[k−1][i],ST[k−1][i+2k−1]).ST[k][i]=\min(ST[k-1][i],ST[k-1][i+2^{k-1}]).

每层至多n项，共O(log(n+1))层，所以预处理和空间均为O(n log(n+1))。构造时只写右端不超过n的有效块，避免把补齐的假元素混入最小值。

查询长度L=r−l，取k=⌊log₂L⌋。读取 [l,l+2^k) 和 [r-2^k,r) 的摘要。两块都在目标区间内，且2·2^k≥L，所以没有中间缺口；二者可能重叠，但min重复同一元素不改变结果。因此只需两次读取和一次min，查询O(1)。k通过整数bit_length计算，不使用浮点对数猜测2次幂边界。

重叠要求幂等

设目标区间被分成X、Y、Z，其中Y为两块重叠部分。两个摘要再合并得到XYYZ；结合律允许重新加括号，幂等律使Y与Y合并回Y，才恢复XYZ。这里需要的是结合与幂等，不额外要求交换；本篇min当然也可交换。

求和没有幂等性。数组 [1,2,3] 查询全部区间时，两块长度2的和分别为3与5，相加得到8，而正确和为6，中间元素2被重复计入。若改成互不相交的2幂块，可以O(log(n+1))次合并求和；但那已不是本节两块O(1)公式。

一次单点更新也可能影响许多预处理项。Sparse Table没有承诺动态更新的对数界；需要持续更新时，应回到11或12篇的结构。静态的含义是查询阶段数据不变，不是“查询比较多”。

最近公共祖先变成最低深度位置

给定n个节点的有根树，每个节点只有一个父亲，根父亲为−1。查询(u,v)返回同时为u、v祖先且深度最大的节点，节点本身也是自己的祖先。构造时验证恰有一个根、父索引合法、无环且所有节点从根可达；非法结构抛ValueError，查询越界抛IndexError。空父数组不是一棵有根树，应拒绝。

完整Euler遍历在第一次进入节点时记录它，每从一个孩子返回父亲时再记录父亲。n个节点、n−1条树边，每条边下行上行各一次，因此记录长度为2n−1。同步保存每次出现的深度，以及每个节点的首次出现位置first。

例如根0有孩子1、2，节点1有孩子3，完整序列为

1
2
3
节点: 0 1 3 1 0 2 0
深度: 0 1 2 1 0 1 0
首次: 0->0, 1->1, 3->2, 2->5

查询3与2时，在首次位置2到5之间找深度最小处，闭区间对应半开 [2,6)，得到节点0。查询1与3则在 [1,3) 得到1。只记录每个节点第一次进入的preorder会丢掉返回父亲的记录：上例首次进入序列是0、1、3、2，3与2之间最低深度只剩节点2，错误地把2当祖先。

正确性来自DFS的子树连续性。设w=LCA(u,v)，且u的首次出现较早。从u首次出现走到v首次出现，遍历不可能离开w的子树后再回来，因为离开表示w子树已处理完；期间必然经过w，或u本身就是w。所有区间内记录的深度不小于w，至少一处等于w，所以深度argmin对应w。

遍历与查询各花多少

本实现用显式栈产生Euler序列，避免链状树超过Python递归限制。遍历O(n)，深度数组长2n−1，再建立Sparse Table需要O(n log(n+1))时间和空间；一次LCA只做常数次first读取与RMQ。静态树结构若改变，原first和深度序列失效，本篇没有动态link/cut接口。

这是一般RMQ的Sparse Table解法，不是原论文利用相邻深度差为±1获得线性预处理的完整最优实现。引用LCA归约不意味着教学代码自动具有论文中其他算法的界。数组元素比较若非单位成本，预处理与查询还须计入比较成本；节点索引和深度按字长可容纳的整数处理。

参照要避开同一种归约

教学实现位于 examples/advanced-algorithms/static_rmq.py，有限差分用例位于同目录的 check_static_rmq.py。本轮未执行第 13 篇检查，不据此声称运行通过；核查记录保留该证据缺项。LCA的独立参照沿u向根收集祖先，再沿v向根找到第一个命中者。它不使用Euler序列或RMQ，因此能发现首次位置、返回记录、区间右端加1等错误。Sparse Table则单独与线性扫描的最左最小值位置对照，避免两层错误恰好互相抵消。

复跑入口如下，命令供具备允许运行环境的读者使用；它不是本轮执行记录。

1
python3 examples/advanced-algorithms/check_static_rmq.py

用例覆盖最左并列最小值、空查询、非法父数组、链和星形树、非零根，以及从独立父链参照得到的 LCA。有限域差分即使通过，也不能证明任意规模的复杂度界。本篇的预处理、查询界均为上述计算模型中的确定性最坏界，不涉及随机期望或高概率保证。

接口与验证边界

练习

  1. 为一棵四节点链写完整Euler序列和first，计算任意两点LCA。若查询两个节点相同，RMQ区间长度为何仍是1而不是0？
  2. 把聚合从min改成字符串连接，用一个长度3的输入演示重叠造成的重复。再说明改成按位或为什么可以使用两块公式。

参考资料