稀疏表

Sparse Table 为每个起点和二次幂尺度保存静态区间摘要。一般查询用二进制分解选取不重叠块；幂等运算允许故意让两个最大块重叠，因为重复的整个交叠摘要不会改变结果。

常见的 min、max、gcd 都是半格理路半格Semilattice · Meet-semilattice · Join-semilattice由交换、结合、幂等运算刻画的单侧格结构。运算，所以教材常把常数查询描述为“半格情形”。半格是充分条件，却比算法真正需要的幂等半群更强。

图左的数字表示下标范围；右图按零基闭区间 $[1,6]$ 聚合数值，得到最小值 $1$。若按 RMQ 的位置接口查询半开区间 $[1,7)$，下文的数对摘要会返回下标 $5$。

稀疏表把静态区间预计算为 $2^k$ 长度块，幂等运算可用两个重叠块常数回答；线段树理路线段树Segment tree把区间递归分解为规范节点，并在每个节点保存幺半群聚合值的平衡树结构。把区间分成不重叠节点并支持更新。前者的常数查询依赖静态性和运算性质，不能靠重建少量表项获得同样的动态接口。

区间最小值查询中，

即使两个块重叠也不会重复计错。区间和不幂等，重叠部分会被加两次，只能使用不重叠分解、前缀和或其他结构。

非交换幂等半群同样可以使用双块公式，只要两块内部和最终合并都保持数组顺序。左零 band $x\circ y=x$ 是形式上的例子；实践中更常见的是交换操作。若实现把两块次序交换，非交换实例会立即暴露错误。

数组更新会使覆盖该位置的许多预计算块失效，Sparse Table 因而适合静态查询。所谓 “Disjoint Sparse Table” 采用另一种预处理，可对一般结合运算提供 $O(1)$ 查询；它不是本页标准重叠结构的自动推论，应单独声明构造与空间。

RMQ理路静态区间最值查询（RMQ）Range minimum query · RMQ预处理静态数组后，返回区间最小元素的位置并固定并列规则。要求返回最左最小值的下标。为实现这个接口，把第 $i$ 个输入摘要取为 $(A[i],i)$，合并使用字典序最小值：先比较数组键，键相等时选择较小下标。这个运算仍结合且幂等，查询后返回摘要的下标分量即可。RMQ 的零基半开区间 $[l,r)$ 对应本页的闭区间 $[l,r-1]$。标准 Sparse Table 用 $O(n\log (n+1))$ 预处理、空间换 $O(1)$ 查询。线性空间常数时间 RMQ理路线性预处理常数时间 RMQConstant-time RMQ · Farach-Colton–Bender RMQ · 线性 RMQ将一般静态 RMQ 归约为深度差为正负一的数组，再用微块类型查表与宏块稀疏表实现线性预处理、常数查询。则通过 Cartesian tree、$\pm 1$ 结构和微块分类降低空间，不能与 Sparse Table 等同。

它与二进制倍增表理路二进制倍增Binary lifting · Doubling technique预计算函数的 $2^k$ 次迭代，用输入步数的二进制展开快速跳转。都使用二次幂尺度，但并不调用祖先跳表；本页表项递推的正确性来自半群结合律，重叠查询的正确性来自幂等性。算法复杂度、代数契约与静态更新假设是三项独立条件，缺一项都不能从另外两项推出。

同样面对静态数组，莫队算法理路莫队算法Mo's algorithm · Mo algorithm · 莫队把静态区间查询按左端块和右端排序，维护可逆窗口状态，并分别核算两端移动、排序和输出成本。还要求查询全部已知，并能低成本增删窗口两端；它重排请求以复用完整频次状态，适合不同值数、同值位置对等不便用两个小摘要合并的统计。无需修改数组不代表满足幂等性，也不代表允许提前取得全部查询。