RMQ(Range Minimum/Maximum Query)问题是指：对于长度为n的数列A，回答若干询问RMQ(A,i,j)(i,j<=n)，返回数列A中下标在[i,j]里的最小(大)值。
最简单的算法我就不解释了，直接搜。但是对于数据量非常大时，这种方法并不适用。所以我们可以使用线段树来记录这个最大（小）值，效率咋算我还不是很了解，反正是一个nlogn形式的。但是线段树的建立和查询都是这个效率。不过有一个更好的方法，那就是ST算法（Sparse Table）：它是一种动态规划的方法。以最小值为例。a为所寻找的数组，用一个二维数组f(i,j)记录区间[i,i+2^j-1]区间中的最小值。其中f[i,0] = a[i];
所以，对于任意的一组(i,j)，f(i,j) = min{f(i,j-1),f(i+2^(j-1),j-1)}来使用动态规划计算出来。
这个算法的高明之处不是在于这个动态规划的建立，而是它的查询：它的查询效率是O(1)！如果不细想的话，怎么弄也是不会想到有O（1）的算法的。假设我们要求区间[m,n]中a的最小值，找到一个数k使得2^k<n-m+1，这样，可以把这个区间分成两个部分：[m,m+2^k-1]和[n-2^k+1,n]！我们发现，这两个区间是已经初始化好的！前面的区间是f(m,k)，后面的区间是f(n-2^k+1,k)！这样，只要看这两个区间的最小值，就可以知道整个区间的最小值！
不得不佩服想出这个算法的人啊！
具体的代码可以看poj 3264。
不过还是要说几个注意的地方：
开辟这个二维数组f的时候注意其第二维不要开的过大，因为2的指数会很大的，到时候在自己机器上都无法运行。
在动态规划计算数组f的时候，用对2取对数来计算上面说的k，那样速度好一点。计算出k后，注意对循环控制变量的范围控制，而且一旦超出了范围，那么该值便不必计算。
算指数的时候可以用>>和<<来计算，不过注意加括号。
在查询的时候，k值仍然可以用对2取对数。
例程：pku 3264
#include<iostream>
#include<stdio.h>
#include<math.h>
using namespace std;
#define maxn 50001
int a[maxn];
int dpmax[maxn][40];
int dpmin[maxn][40];
int getmin(int a,int b)
{
if(a<b) return a;
else return b;
}
int getmax(int a,int b)
{
if(a>b) return a;
else return b;
}
void Make_Big_RMQ(int n)
{
int i,j,k;
for(i=1;i<=n;i++) dpmax[i][0]=a[i];
for(j=1;j<=log((double)n)/log(2.0);j++)
for(i=1;i+(1<<j)-1<=n;i++)
{
dpmax[i][j]=getmax(dpmax[i][j-1],dpmax[i+(1<<(j-1))][j-1]);
}
}
void Make_Min_RMQ(int n)
{
int i,j,k;
for(i=1;i<=n;i++) dpmin[i][0]=a[i];
for(j=1;j<=log((double)n)/log(2.0);j++)
for(i=1;i+(1<<j)-1<=n;i++)
{
dpmin[i][j]=getmin(dpmin[i][j-1],dpmin[i+(1<<(j-1))][j-1]);
}
}
int get_big_rmq(int a,int b)
{
int k=(int)(log((double)(b-a+1))/log(2.0));
return getmax(dpmax[a][k],dpmax[b-(1<<k)+1][k]);
}
int get_min_rmq(int a,int b)
{
int k=(int)(log((double)(b-a+1))/log(2.0));
return getmin(dpmin[a][k],dpmin[b-(1<<k)+1][k]);
}
int main()
{
int n,m,i,j,k,q,x,y;
while(scanf("%d%d",&n,&q)!=EOF)
{
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
Make_Big_RMQ(n);
Make_Min_RMQ(n);
for(i=1;i<=q;i++)
{
scanf("%d%d",&x,&y);
printf("%d\n",get_big_rmq(x,y)-get_min_rmq(x,y));
}
}
return 0;
}