RMQ区间最值查询

kirito 收录于类别 algorithm

2019-01-20 2019-01-20 约 677 字预计阅读 2 分钟次阅读条评论

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])

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30


#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 表示一个区间

输出每个区间内最大值减去最小值是多少

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


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

ac代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42


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

目录

RMQ区间最值查询

思路：

例题