区间---RMQ区间最值查询

RMQ区间最值查询，对于长度为n的数组A[]。
RMQ(i,j)，返回数组A区间[i , j]内的最大值或最小值。

思路：

ST算法：
O(nlogn)预处理，O(1)查询
定义dp[i][j]表示从第i个数起连续2^j个数中(即区间[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])
查询：如果查询区间[i,j]内的最值，先求区间长度为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 表示一个区间
输出每个区间内 最大值 减去 最小值 是多少

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