RMQ用于求区间最值问题。需要O(nlogn)的预处理时间，查询时间为O(1)，用于解决大量查询的时间复杂度优化，是一个很简单的算法，思路很好想，代码也不长，很好写。
在讲解之前需要注意的点：
1.数组下标从0开始。
2. i 代表的是长度下标， j 代表的是2的幂数，2^j 代表下标。
附下图（我临摹地可能不好额emmmm）
d[i][j]表示从i开始的，长度为2^j的一段元素中的最值。
递推公式：d[i][j] = min(d[i][j-1] , d[i+2^(j-1)][j-1])
由于 2^j <= n，所以j <= logn，可以推出d数组的元素个数不超过nlogn
模板代码如下：
const int maxn = 1e5+10;
int d[maxn][20];
void RMQ_init(const vector<int>& A){
int n = A.size();//A是一开始给出的数组
for(int i = 0;i < n;i++) d[i][0] = A[i];//初始化
for(int j = 1;(1<<j) <= n;j++){//j是从1开始，因为上面初始化时用了j=0
for(int i = 0;i+(1<<j)-1 < n;i++){//i从0开始，小于n
d[i][j] = max(d[i][j-1],d[i+(1<<(j-1))][j-1]);//递推公式
}
}
}
//查询操作
int RMQ(int L,int R){
int k = 0;
while((1<<(k+1)) <= R-L+1) k++;
return max(d[L][k],d[R-(1<<k)+1][k]);//用两个区间一起比较查询，有重复
}
提供一个运用RMQ写的例题，UVA11235，（虽然也可以用线段树写）
具体做法网上有很多，我推荐一个链接：
京公网安备 11010502036488号