RMQ算法适合求解对一个数组多次查询给定范围内的最值。
预处理操作：
令d[i,j]表示从i开始，长度为2^j的一段元素的最值，可以用递推公式写出d[i,j] = min{ d[i][j-1], d[ i+2^(j-1) ][j-1] }
原理如图所示：
复杂度：因为2^j<=n， 所以d数组的元素不会超过nlogn个， 计算每个d[][]需要O（1）。所以总的时间复杂度是O（nlogn）
查询操作：找到一个最大的整数k,使2^k<=R-L+1，这样查询区间就可以分为 i~i+2^k-1 和 j-2^k+1 ~ j 2个区间。因为是求最值，所以区间有一些重复也没有关系。
//d[i][j] 表示 i往后2^j 区间内的最值
void RMQ_init(int *A,int n)
{
for(int i=; i<n; i++) d[i][]=A[i]; //初始化
// 极端情况 i=0; d[0][j-1]要求(1<<j)-1 < n
for(int j=; (<<j)- < n; j++)
// d[i][j-1] 要求 i+(1<<j)-1 < n
for(int i=; i+(<<j)- < n; i++)
d[i][j]=MAX( d[i][j-], d[i + (<<(j-))][j-] );
} int RMQ(int L, int R)
{
int k=;
while( <<(k+) <= R-L+ ) k++;
// 2段有重合，但是求最值不影响
return MAX( d[L][k], d[R-(<<k) + ][k] );
}