?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;???
}