范围最值查询

范围最值查询（英语：Range Minimum Query），是针对数据集的一种条件查询。若给定一个数组，范围最值查询指定一个范围条件到，要求取出中最大／小的元素。
若，条件为的范围最值查询返回1，它是子数组中最小的元素。
通常情况下，数组A是静态的，即元素不会变化，例如插入、删除和修改等，而所有的查询是以在线的方式给出的，即预先并不知道所有查询的参数。
RMQ问题有预处理之后每次查询的算法。
范围最值查询问题（RMQ）与最近公共祖先(图论)（LCA）问题有直接联系，它们可以互相转化。RMQ的算法常常应用在严格或者近似子串匹配等问题的处理中。

Sparse Table

创建一个二维数组 的整数值。
在这个数组中 表示范围 中的最大值（例如  中的最大值被计为）。

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

// 长度为0 时，表示数据自身。
for (int i = 0; i < Length; ++i) F[i][0] = Array[i];

for (int j = 1; (1 << j) <= Length; ++j)
for (int i = 0; i + (1 << j) - 1 < Length; ++i)
F[i][j] = min(
F[i][j - 1], F[i + (1 << (j - 1))][j - 1]
); // 分成长度相等的两段}
当我们需要计算一个区间中的最大值（例如  时），我们先求出这个区间的长度（即 8 - 3 + 1 = 6）。
然后我们算出不大于它的最大 值的指数（即 2）。我们要查询分别以3 开头，和以8 结尾的两个长度为 的区间的最大值。

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

while (1 << (i + 1) <= Right - Left + 1) ++i;

return min(
F[Left][i], F[Right - (1 << i) + 1][i]
);}
整个程序的时间复杂度是，Q 为查询数。