RMQ(Range Minimum/Maximum Query)问题是求区间最值问题。
对于长度为 n 的数组 A，进行若干次查询，对于区间 [L,R] 返回数组A中下标在 [L,R] 中的最小（大）值。
可以用线段树来解决这个问题，预处理的复杂度是 O(nlogn)，查询的复杂度是 O(logn)。
更好的解法是ST算法。Sparse_Table算法，即稀疏表算法，这个方法可以在 O(nlogn) 的预处理后达到 O(1) 的查询代价。
这个算法非常容易实现。
定义 F[ i, k ] 表示从 i 开始的，长度为 2^k 的区间内元素的最小值。
当 k = 0 时，F[ i, 0 ] 的值显然就是A[ i ] 的值。
而 k > 0 时，对于从 i 开始的长度为 2^k 的区间，它的最小值显然是从 i 开始的长度为 2^(k-1) 的区间中的最小值与从 i+2^(k-1)开始的长度为 2^(k-1) 的区间中的最小值中更小的那一个。
则有递推公式 F[ i, k ] = min{ F[ i, k-1 ], F[ i+2^(k-1), k-1] }
由于 2^k<=n，因此 F 数组中的元素个数不会超过 nlogn，而每个元素都可以在O(1)的时间内计算出，因此总时间为O(nlogn)。
int F[maxn][];
//元素从1编号到n
void RMQ_init(int A[],int n){
for (int i=;i<=n;i++) F[i][]=A[i];
for (int k=;(<<k)<=n;k++)
for (int i=;i+(<<k)-<=n;i++)
F[i][k]=min(F[i][k-],F[i+(<<(k-))][k-]);
}
RMQ的预处理
对于查询操作 [L,R]，定义 k 为满足 2^k<=R-L+1 的最大整数。
则以L开头的长度为 2^k 的区间与以R结尾的长度为 2^k 的区间，能够完整的覆盖区间 [L,R]。
因此这两个区间的最小值中更小的那一个就是所查询的区间 [L,R] 的最小值。
int RMQ(int L,int R){
int k=;
while ((<<(k+))<=R-L+) k++;
return min(d[L][k],d[R-(<<k)+][k]);
}
RMQ查询
ST 算法也可以求出最值所在的下标，只要将 F 数组中储存的值变为数组 A 的下标即可。