范围最值查询

范围最值查询（），是针对数据集的一种条件查询。若给定一个数组A[1, n]，范围最值查询指定一个范围条件i到j，要求取出A[i, j]中最大／小的元素。

若A = [3, 5, 2, 5, 4, 3, 1, 6, 3]，条件为[3, 8]的范围最值查询返回1，它是子数组A[3, 8] = [2, 5, 4, 3, 1, 6]中最小的元素。

通常情况下，数组A是静态的，即元素不会变化，例如插入、删除和修改等，而所有的查询是以在线的方式给出的，即预先并不知道所有查询的参数。

RMQ问题有预处理O(n)之后每次查询O(1)的算法。

范围最值查询问题（RMQ）与最近公共祖先（LCA）问题有直接联系，它们可以互相转化。RMQ的算法常常应用在严格或者近似子串匹配等问题的处理中。

算法
Sparse Table
建立一个二维数组 F[1 \dots N][0 \dots O(\log_2 N)] 的整数值。

在这个数组中 F[i][j] 表示范围 [i, i+2^j-1] 中的最大值（例如 [2, 5] 中的最大值被计为 F[2][2]）。

建立数组的过程可以在 O(N \log N) 时间内完成。具体算法类似于动态规划。以下是 C++ 语言描述的代码，数组约定从 0 开始：
void Initialise(vector &Array)
{
int Length = (int)Array.size();

// 长度为 0 时，表示数据自身。
for (int i = 0; i 当我们需要计算一个区间中的最大值（例如 [3, 8] 时），我们先求出这个区间的长度（即 8 - 3 + 1 = 6）。

然后我们算出不大于它的最大 2^k 值的指数（即 2）。我们要查询分别以 3 开头，和以 8 结尾的两个长度为 2^2 的区间的最大值。

显然 F[3][2] 和 F[5][2] 也就是（[3, 6] 和 [5, 8]）的最大值就是 [3,8] 的最大值。查询的时间是常数，代码如下：
int Query(int Left, int Right)
{
int i = 0;

while (1 程序预处理的时间复杂度是 O(N \log N)的，单次询问的时间复杂度是O(1)的。整个程序的空间复杂度是O(N \log N)。

Method of Four Russians
先对数组进行分块，再预处理出每个块里的ST表，以及每个块的最值构成的数组的ST表。然后每次查询时，只需算出中间连续几个块的最小值与两边不完整的块的最小值的最小值。程序预处理的时间复杂度是 O(N \log\log N)的，单次询问的时间复杂度是O(1)的。整个程序的空间复杂度是O(N \log\log N)。还可以再优化，使预处理的时间复杂度是 O(N)的，单次询问的时间复杂度是O(1)的，空间复杂度是O(N)。

数据结构
如果使用线段树等数据结构，则可以做到预处理的时间复杂度是 O(N \log N)，单次询问的时间复杂度是O(\log N)。整个程序的空间复杂度是O(N)。优点是可以支持动态修改。

应用
在Fischer和Heun（2007）中可以找到一些应用。

计算树中的最近公共祖先
范围最值查询可被用于解决最近公共祖先问题。有根树S中的节点v与w的最近公共祖先是在从根到w和v的路径上最深的公共节点u（其可能是v或w）。 Gabow, Bentley和Tarjan（1984）表明，最近公共祖先问题可以在线性时间内规约到范围最值查询问题。由此可见，与范围最值查询问题一样，最近公共祖先问题可以在常数时间内进行单次查询，并仅使用线性空间。

参考资料