线性预处理常数时间 RMQ

形式陈述 ​

接口与归约后的规模 ​

给定长度 $n\ge 1$ 的静态数组 $A$，回答RMQ理路静态区间最值查询（RMQ）Range minimum query · RMQ预处理静态数组后，返回区间最小元素的位置并固定并列规则。：对 $0\le l<r\le n$，返回半开区间 $[l,r)$ 的最左最小值位置。空数组没有合法的非空查询，可以直接保存空结构。假设键比较为常数时间，机器字能容纳下标，并在Word-RAM理路Word-RAM 模型Word RAM · Word-RAM model以 w 位机器字、常数时间随机访存和明确字级操作集分析算法的随机访问机模型。上支持常数时间位运算和表寻址。目标是 $O(n)$ 预处理、$O(n)$ 字空间和 $O(1)$ 最坏查询。

先按 $(A[i],i)$ 的字典序建立最小笛卡尔树 $C(A)$。RMQ–LCA 归约理路RMQ 与 LCA 的等价归约RMQ-LCA equivalence · RMQ to LCA reduction用 Euler 深度序列与 Cartesian tree 建立静态 RMQ 和 LCA 的双向线性归约。给出

完整 Euler walk 记录顶点 $E[j]$、深度 $D[j]$ 和每个顶点首次出现位置。令

相邻两次记录沿一条树边上下移动，所以 $D[j+1]-D[j]\in \{-1,+1\}$。两顶点首次位置之间的最小深度记录对应其 LCA。树、walk 和首次位置表均可在线性时间构建；下面所有微块数量都按实际深度数组长度 $m$ 计算。

微块类型与查表 ​

常数小的 $m$ 直接处理。其余情况取

并把 $D$ 分成长度至多 $b$ 的连续块。满块减去首深度后，只由 $b-1$ 个正负一增量决定，因此共有 $2^{b-1}=O(\sqrt{m})$ 种类型。

每种类型的所有相对区间 $[p,q)$ 都有固定的最左最小位置。先还原它的相对深度，再对每个起点逐步延长右端、维护当前最左最小位置，就能在 $O(b^2)$ 时间填好该类型的所有答案。全部微表的时间与空间为

最后一个短块按长度和类型共同编号；把所有较短长度也求和，仍为 $O(2^b{b}^2)$。

类型编码占至多 $b-1$ bit，实际块还保存首深度和全块最小值位置。类型与两个块内端点可放入常数个机器字，一次局部查询通过表寻址取得相对位置，再加上块起点。扫描时同时为每个位置记录所属块号和块内偏移，查询便不依赖额外的常数时间整数除法。实际块的编码、位置表与最小值扫描总计 $O(m)$ 工作。

宏结构 ​

实际微块数是

宏数组 $M[j]$ 保存第 $j$ 块的最左最小位置，并按 $(D[M[j]],M[j])$ 比较。对这 $N$ 项建立稀疏表理路稀疏表Sparse table预计算长度为二次幂的静态区间答案，以 $O(1)$ 或 $O(\log n)$ 回答区间查询。，其预处理和空间为

因为 $b=\mathrm{\Theta }(\log m)$，宏数组缩小了一个对数因子。同时为宏区间长度预存下整对数，宏查询只需常数次表访问和比较，返回连续完整块中的最左最小位置。

总成本由一般数组归约 $O(n)$、实际深度块扫描 $O(m)$、通用微表 $o(m)$ 和宏表 $O(m)$ 组成。用 $m=2n-1$ 换回原输入规模，得到 $O(n)$ 预处理和空间。