时间戳

首页 > 技术文章 > RMQ (Range Minimum/Maximum Query)

RMQ (Range Minimum/Maximum Query)

Uninstalllingyi 2019-08-26 11:09 原文

 Range Minimum/Maximum Query

别名S(Sparse)T(Table)表。直译稀疏表表

这是个什么东西？可以理解为一种题型。用来求某个区间内的最大值或最小值，通常用在需要多次询问一些区间的最值的问题中。隶属于动规DP

这主要针对于区间内最大值或最小值，不需要修改的题型。需要修改的话，请右转线段树。

引题描述

 输入N个数和M次询问，每次询问一个区间[L,R],求第L个数到R个数之间的最大值。 

题析

用A[1..N]表示一组数，F[I,J]表示从A[I]到A[I+2^J-1]这个范围内的最大值，也就是以A[I]为起点连续2^J个数的最大值，由于元素个数为2^J个，所以从中间平均分成两部分，每一部分的元素个数刚好为2^(J-1)个，如下图：

 

整个区间的最大值一定是左右两部分最大值的较大值，满足动态规划的最优原理
状态转移方程：

F[I,J]=max(F[I,J-1],F[I+2^(J-1),J-1])
边界条件为F[I,0]=A[I]

1<=j<=floor(log2(n))

1<=i<=n-2^i+1

这样就有效防止了i的溢出，j的向下取整也保证了其不会超出区间最右端的范围
这样就可以在O(NlgN)的时间复杂度内预处理F数组。

题目中的ShowTime

高度平衡 Balanced Lineup  USACO 2007 January Silver 

题来

板子题不绕弯，直接上代码了

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int MAXN=50010;
int n,q;
int Height[MAXN];
int RMaxQ[MAXN][20];
int RMinQ[MAXN][20];
int main(){
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++){
        scanf("%d",&Height[i]);
        RMinQ[i][0]=Height[i];
        RMaxQ[i][0]=Height[i];
    }
    for(int j=1;j<=floor(log2(n));j++){
        for(int i=1;i<=(n-(1<<j)+1);i++){
            RMinQ[i][j]=min(RMinQ[i][j-1],RMinQ[i+(1<<(j-1))][j-1]);
            RMaxQ[i][j]=max(RMaxQ[i][j-1],RMaxQ[i+(1<<(j-1))][j-1]);
        }
    }
    int a,b,k;
    int a1,a2;
    for(int i=1;i<=q;i++){
        scanf("%d%d",&a,&b);
        k=floor(log2(b-a+1));
        a1=min(RMinQ[a][k],RMinQ[b-(1<<k)+1][k]);
        a2=max(RMaxQ[a][k],RMaxQ[b-(1<<k)+1][k]);
        printf("%d\n",a2-a1);
    }
}

 奶牛探洞  USACO OPEN2004 

第二道板子题，稍作修改就行了。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int MAXN=26000;
int n,q;
int Width[MAXN];
int RMQ[MAXN][20];
int main(){
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++){
        scanf("%d",&Width[i]);
        RMQ[i][0]=Width[i];
    }
    for(int j=1;j<=floor(log2(n));j++){
        for(int i=1;i<=(n-(1<<j)+1);i++){
            RMQ[i][j]=min(RMQ[i][j-1],RMQ[i+(1<<(j-1))][j-1]);
            
        }
    }
    int a,b;
    for(int i=1;i<=q;i++){
        scanf("%d%d",&a,&b);
        int k=floor(log2(b-a+1));
        cout<<min(RMQ[a][k],RMQ[b-(1<<k)+1][k])<<endl;
    }
}

 

推荐阅读