011-数据结构-区间最值查询

核心概述：基于稀疏表（Sparse Table）的区间最小值查询（RMQ），一次性预处理 O(n log n)，在区间 [a,b) 上以 O(1) 常数时间返回最小值（或按需改为最大值）。

原文引述：

Description: Range Minimum Queries on an array. Returns min(V[a], V[a + 1], … V[b - 1]) in constant time. Usage: RMQ rmq(values); rmq.query(inclusive, exclusive); Time: $O(|V|\log |V|+Q)$

展开阐述：

• 定义与背景

  • 问题：对静态数组 V 支持多次区间最值查询，要求极快的单次查询时间。
  • 思路：为每个 2^k 的长度预先计算区间最值，查询时将任意长度 L 映射为两个长度为 2^⌊log2 L⌋ 的重叠块，答案为二者最小值。
  • 适用场景：数据静态、查询量大；典型如离线最值统计、稠密询问的在线判定。

• 数据结构与接口（据实现）

  • 存储：
    • jmp[k][i] 表示区间 [i, i + 2^k) 的最小值；第 0 层 jmp[0] 为原数组 V 的拷贝。
    • 预先构建一个以 k 为层的二维表，总层数约为 floor(log2 n) + 1。
  • 构造：
    • 自底向上递推：
      • jmp[k][i] = min(jmp[k-1][i], jmp[k-1][i + 2^{k-1}])。
    • 预处理复杂度与空间：O(n log n)。
  • 查询：
    • 约定区间为半开 [a, b)，需断言 a < b。
    • 令 dep = floor(log2(b - a))，则
      • ans = min(jmp[dep][a], jmp[dep][b - 2^{dep}])。
    • 单次查询 O(1)。

• 关键语义与易错点

  • 区间开闭：本实现以 [a,b) 为语义；若业务使用闭区间 [l,r]，可改为 [l, r+1) 或在调用前统一转换，避免 off-by-one。
  • 对比线段树与树状数组：
    • RMQ 适合静态且仅“最值类”聚合；若需点/区间更新请选用线段树（见 012-数据结构-线段树/006-数据结构-懒标记线段树），若仅做前缀和/点加可用 003-数据结构-树状数组。
  • 边界：b 必须 > a；长度 L = b-a ≥ 1 才有意义；dep 取整必须用 floor(log2 L)。
  • 稳健性：当需要“索引位置”而非“值”时，稀疏表应改存“极值索引”，合并时比较对应值再返回索引。

• 复杂度与边界条件

  • 预处理：O(n log n)；查询：O(1)；空间：O(n log n)。
  • 单调性与幺元：最值函数满足幺半群结合性，但非可逆，因而采用“重叠两块”分解（而非线段树式分解）。
  • 值域与稳定性：如需“稳定极值”（相等时取靠左或靠右），可在构建时定义合并规则以打破平手。

• 变体/扩展

  • RMQ-最大值：将 min 改为 max，公式一致。
  • RMQ-按位或/与：若操作满足幂等与结合律，同样可用两块覆盖法 O(1) 查询。
  • 稀疏表 + 前缀：可并置一个 prefix log 数组以 O(1) 取得 dep，减少调用 log 开销。
  • 滑动窗口最值：若需要在线维护窗口最值且数据动态滑动，考虑单调队列替代。
  • 多维 RMQ：二维场景可用 2D 稀疏表（空间更大，构建 O(nm log n log m)；查询 O(1)）。

• 正确性要点与直觉证明

  • 两块覆盖法：任意长度 L 的区间可被两个长度 2^k、且 k=floor(log2 L) 的区间覆盖（左块 [a, a+2^k)，右块 [b-2^k, b)），二者并集覆盖 [a,b)，交叠区在中间。由于 min 是幂等且满足结合与交换，min([a,b)) = min(min(左块), min(右块))。
  • 不变式：第 k 层的每一项均正确表示该长度区间的最小值，层间递推使用两个半区间的最小值合成，归纳成立。

• 与相邻技术的对比与取舍建议

  • 003-数据结构-树状数组：适合点加/前缀和；无法直接做最值。
  • 012-数据结构-线段树：支持点/区间更新与多类聚合，但查询 O(log n)；静态 RMQ 大规模查询时，稀疏表更优。
  • 006-数据结构-懒标记线段树：适合需要区间加/覆盖与最值混合操作；代价是实现复杂度与常数更大。

• 极简伪代码（仅示意）

  • 预处理：
    • jmp[0] = V
    • for k in [1 .. K]:
      • for i in [0 .. n - 2^k]:
        • jmp[k][i] = min(jmp[k-1][i], jmp[k-1][i + 2^{k-1}])
  • 查询：
    • L = b - a; k = floor(log2 L)
    • return min(jmp[k][a], jmp[k][b - 2^k])

关联节点

• 012-数据结构-线段树
• 003-数据结构-树状数组
• 006-数据结构-懒标记线段树