RMQ算法

RMQ问题为： 给一个长度为 n 的数组 A ， 回答询问 RMQ( A, i, j )， 即 A[i] 到 A[j] 之间的最小或最大的数的下标。

 

用 dp[i,j] 表示从 i 开始，长度为 2^j 的区间内的最小或最大值，区间[i,j] 可以划分为区间 [i, i+ 2^(j-1)] 与区间

[i+ 2^(j-1), i+ 2^j] 的并，所以 dp[i][j]= min{ dp[i][j-1], dp[i+ 2^(j-1)][j-1] }。这样就能在 nlogn 的时间内预处理所有[i, i+ x^j] 的区间内的最值。对于询问 [a, b] 间的最值， 只要找到一个 d, 满足 2^d<= b- a， 这样区间[a,b]就可以划分为区间 [a, a+ 2^d] 与 区间 [b- 2^d, b] 的并， 所以 [a, b] 的最值就是 min{ dp[a][d], dp[b- 2^d][d] }。

 

代码：

int dp[N][32], data[N];
void init(){
    for( int i= 0; i< n; ++i ) dp[i][0]= data[i];
    for( int i= 1; 1<<i < n; ++i )
    for( int j= 0, s= 1<<(i-1); j+ s< n; ++j )
    dp[j][i]= max( dp[j][i-1], dp[j+s][i-1] );
}
int rmq( int a, int b ){
    int d= b- a+ 1, t= 0;
    while( 1<<t <= d ) t++; t--;
    return max( dp[a][t], dp[b-(1<<t)+1][t] );
}

POJ  3264  Balanced Lineup  为RMQ的应用

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>

using namespace std;

#define N 50001

int dp[N][32], data[N], d[N][32];
int n, m;

void init(){
    for( int i= 0; i< n; ++i ) { dp[i][0]= data[i]; d[i][0]= data[i]; }
    for( int i= 1; 1<<i < n; ++i )
    for( int j= 0, s= 1<<(i-1); j+ s< n; ++j ){
        dp[j][i]= max( dp[j][i-1], dp[j+s][i-1] );
        d[j][i]= min( d[j][i-1], d[j+s][i-1] );
    }
}
int rmq( int a, int b ){
    int dist= b- a+ 1, t= 0;
    while( 1<<t <= dist ) t++; t--;

    return max( dp[a][t], dp[b- (1<<t)+1][t] )- min( d[a][t], d[b-(1<<t)+1][t] );
}

int main(){
    scanf("%d%d",&n,&m);
    for( int i= 0; i< n; ++i ) scanf("%d", data+ i );
    
    init();
    for( int i= 0; i< m; ++i ){
        int a, b;
        scanf("%d%d",&a,&b ); a--; b--;
        printf("%d\n", rmq( a, b ) );
    }
    
    return 0;
}