RMQ區(qū)間最值查詢浪藻，對于長度為n的數組A[]戏仓。
RMQ(i,j)，返回數組A區(qū)間[i , j]內的最大值或最小值扒最。

思路：

ST算法：
O(nlogn)預處理，O(1)查詢
定義dp[i][j]表示從第i個數起連續(xù)2^j個數中(即區(qū)間[i...i+2^j-1])的最值
如A={0,1,2,3},dp[0][1]=1,dp[0][2]=3.這里求最大值
初始化dp[i][0] = A[i]
轉移方程：dp[i][j] = max(dp[i][j-1], dp[i+2^(j-1)][j-1])
查詢：如果查詢區(qū)間[i,j]內的最值华嘹，先求區(qū)間長度為j-i+1
令k = log2(j-i+1)吧趣，則RMQ(i,j) = max(dp[i][k], dp[j-(2^k)+1][k])

#include <iostream>
using namespace std;
namespace RMQ{
    int *A;
    int dp[100][10];//第二維大小log2(n)就行
    void init(int n){//數組長度
        for(int i=0; i<n; i++){
           dp[i][0] = A[i]; 
        }
        for(int j=1; (1<<j)<=n; j++){
            for(int i=0; i+(1<<j)-1<n; i++){
                dp[i][j] = max(dp[i][j-1], dp[i+(1<<(j-1))][j-1]);
            }
        }
    }
    int query(int l, int r){
        int k=0;  //k=log2(r-l+1)
        while((1<<k+1) <= r-l+1) k++;
        return max(dp[l][k] ,dp[r-(1<<k)+1][k]);
    }
}
int main(){
     int data[] = {3 ,2 ,4 ,5 ,6 ,8 ,1 ,2 ,9 ,7};
     RMQ::A=data;
     RMQ::init(10);
     cout<<RMQ::query(0,9)<<endl;//3....7 -> 9
     cout<<RMQ::query(1,1)<<endl;//2 -> 2
     cout<<RMQ::query(4,6)<<endl;//6 8 1 -> 8
     return 0;
}

例題

POJ3264
題目大意：
第一行輸入 n,q 表示一個長度為n的數列，q組詢問
接下來n行 每行一個整數表示數列內容
接下來q行 每行一個l r 表示一個區(qū)間
輸出每個區(qū)間內 最大值 減去 最小值 是多少

Sample Input
1
7
3
4
2
5
1 5
4 6
2 2
Sample Output
6
3
0

ac代碼

#include <iostream>
#include <stdio.h>
using std::max;
using std::min;
namespace RMQ{
    int *A;
    int dp[50000][32];
    int dp2[50000][32];
    void init(int n){//數組長度
        for(int i=0; i<n; i++){
           dp[i][0] = A[i];
           dp2[i][0] = A[i];
        }
        for(int j=1; (1<<j)<=n; j++){
            for(int i=0; i+(1<<j)-1<n; i++){
                dp[i][j] = max(dp[i][j-1], dp[i+(1<<(j-1))][j-1]);
                dp2[i][j] = min(dp2[i][j-1], dp2[i+(1<<(j-1))][j-1]);
            }
        }
    }
    int query(int l, int r){
        int k=0;  //k=log2(r-l+1)
        while((1<<k+1) <= r-l+1) k++;
        return max(dp[l][k] ,dp[r-(1<<k)+1][k])-min(dp2[l][k] ,dp2[r-(1<<k)+1][k]);
    }
}
int data[50000];
int main(){
    int n,q;
    scanf("%d %d",&n,&q);
    for(int i=0;i<n;++i){
        scanf("%d",&data[i]);
    }
    RMQ::A=data;
    RMQ::init(n);
    int l,r;
    while(q--){
        scanf("%d %d",&l,&r);
        printf("%d\n",RMQ::query(l-1,r-1));
    }
     return 0;
}