
_START_ARTICLE_
范围最值查询
_START_PARAGRAPH_
范围最值查询（英语：Range Minimum Query），是针对数据集的一种条件查询。若给定一个数组，范围最值查询指定一个范围条件到，要求取出中最大／小的元素。_NEWLINE_若，条件为的范围最值查询返回1，它是子数组中最小的元素。_NEWLINE_通常情况下，数组A是静态的，即元素不会变化，例如插入、删除和修改等，而所有的查询是以在线的方式给出的，即预先并不知道所有查询的参数。_NEWLINE_RMQ问题有预处理之后每次查询的算法。_NEWLINE_范围最值查询问题（RMQ）与最近公共祖先(图论)（LCA）问题有直接联系，它们可以互相转化。RMQ的算法常常应用在严格或者近似子串匹配等问题的处理中。
_START_SECTION_
Sparse Table
_START_PARAGRAPH_
创建一个二维数组 的整数值。_NEWLINE_在这个数组中 表示范围 中的最大值（例如  中的最大值被计为）。_NEWLINE__NEWLINE_创建数组的过程可以在 时间内完成。具体算法类似于动态规划。以下是C++ 语言描述的代码，数组约定从0 开始：_NEWLINE_void Initialise(vector<int> &Array){_NEWLINE_int Length = (int)Array.size();_NEWLINE__NEWLINE_// 长度为0 时，表示数据自身。_NEWLINE_for (int i = 0; i < Length; ++i) F[i][0] = Array[i];_NEWLINE__NEWLINE_for (int j = 1; (1 << j) <= Length; ++j)_NEWLINE_for (int i = 0; i + (1 << j) - 1 < Length; ++i)_NEWLINE_F[i][j] = min(_NEWLINE_F[i][j - 1], F[i + (1 << (j - 1))][j - 1]_NEWLINE_); // 分成长度相等的两段}_NEWLINE_当我们需要计算一个区间中的最大值（例如  时），我们先求出这个区间的长度（即 8 - 3 + 1 = 6）。_NEWLINE_然后我们算出不大于它的最大 值的指数（即 2）。我们要查询分别以3 开头，和以8 结尾的两个长度为 的区间的最大值。_NEWLINE__NEWLINE_显然  和  也就是（ 和 ）的最大值就是 的最大值。查询的时间是常数，代码如下：_NEWLINE_int Query(int Left, int Right){_NEWLINE_int i = 0;_NEWLINE__NEWLINE_while (1 << (i + 1) <= Right - Left + 1) ++i;_NEWLINE__NEWLINE_return min(_NEWLINE_F[Left][i], F[Right - (1 << i) + 1][i]_NEWLINE_);}_NEWLINE_整个程序的时间复杂度是，Q 为查询数。