范围最值查询（Range Minimum Query），是针对数据集的一种条件查询。若给定一个数组，范围最值查询指定一个范围条件，在满足这个条件的情况下要求取出给定数组中最大或最小的元素。

若，条件为的范围最值查询返回1，它是子数组中最小的元素。

通常情况下，数组A是静态的，即元素不会变化，例如插入、删除和修改等，而所有的查询是以离线的方式给出的，即预先并不知道所有查询的参数。在上述条件下，将数组以特定方式进行预处理即可以使范围最值查询在常数时间内得到处理。

现有算法可以通过以线性时间对数组进行预处理以获得之后常数时间的范围最值查询处理，其空间复杂度为。范围最值查询问题（RMQ）与最低公共祖先（LCA）问题有直接联系，它们可以互相转化。RMQ的算法常常应用在严格或者近似子串匹配等问题的处理中。

RMQ问题的常见解决方法有线段树、ST(倍增)、排序和朴素。

朴素算法就是每次查询都For一遍，时间复杂度。排序法就是新开一个数组记录数的位置，排序后每次查询从头到尾For一遍，找到第一个在区间中的数退出即可。编程复杂度低，但是实际效果可能并不好。最坏情况时间复杂度，但平均情况会比朴素快那么一点。倍增法请参见下面部分。线段树是最快的算法，但是编程复杂度非常高，因此除非数据很大极少使用。

建立一个二维数组的整数值。

在这个数组中表示范围中的最大值（例如中的最大值被计为）。

建立数组的过程可以在 时间内完成。具体算法类似于动态规划。以下是C++语言描述的代码，数组约定从0开始：

当我们需要计算一个区间中的最大值（例如时），我们先求出这个区间的长度（即 8-3+1=6）。

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

显然和也就是（ 和）的最大值就是的最大值。查询的时间是常数，代码如下：

整个程序的时间复杂度是，Q为查询数。