RMQ简单来说就是求区间的最大值（最小值）

核心算法:动态规划

RMQ（以下以求最大值为例）

F[i,j]表示 从 i 开始 到i+2j -1这个区间中的最大值

状态转移方程

F[i,j]=max(f[i,j-1],f[i+2^j-1,j-1])

我们可以把区间[i,i+2j-1]平均分为两个区间，因为j>=1的时候该区间的长度始终为偶数，可以分为区间[i,i+2j-1-1]和区间[i+2j-1-1,i+2j-1]，即取两个长度为2j-1的块取代和更新长度为2j的块;

动归过程为

void ST(int n) {
for(int i=1; i<=n; i++) f[i][0]=a[i];
for(int j=1; (1<<j)<=n; j++) {
for(int i=1; i+(1<<j)-1<=n; i++) {
f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
}
}
}

　　找到各区间的最值之后，由于f[i][j]表示 从 i 开始 到i+2j -1这个区间中的最大值

该如何输出区间[l,r]的最值？

int rmq(int l,int r) {
int j=0;
while((1<<(j+1))<=r-l+1) j++;
return max(f[l][j],f[r-(1<<j)+1][j]);
}

　　完整代码为

#include
#include
#include
using namespace std;
int f[500][500],a[1000];
void ST(int n) {
for(int i=1; i<=n; i++) f[i][0]=a[i];
for(int j=1; (1<<j)<=n; j++) {
for(int i=1; i+(1<<j)-1<=n; i++) {
f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
}
}
}
int rmq(int l,int r) {
int j=0;
while((1<<(j+1))<=r-l+1) j++;
return max(f[l][j],f[r-(1<<j)+1][j]);
}
int main(){
int n,m;
scanf("%d%d",&n,&m);
for(register int i=1;i<=n;++i){
scanf("%d",&a[i]);
}
ST(n);
for(int i=1;i<=m;i++){
int a,b;
scanf("%d%d",&a,&b);
printf("%d",rmq(a,b));
}
return 0;
}