首页 > 其他 > 详细

RMQ

时间:2020-02-22 14:37:46      阅读:52      评论:0      收藏:0      [点我收藏+]

RMQ问题:

RMQ问题是Range Maximum Query的缩写顾名思义就是区间最大值问题,对于这类问题的求解方法是——ST算法,ST算法采用一种类似动态规划的求解方式,可以在O(nlogn)内处理,O(1)询问,但是不支持修改,因此适用于极大数据量的查询问题。

ST:

对于a[1],a[2],a[3],a[4],.......a[n]的n个数的数组,我们用 f[i][j]表示数组a[i],a[i+1],a[i+2].....a[i+2^j-1]的区间最大值,因为区间长度为2^j所以我们可以将区间分成两部分,一部分为a[i],a[i+1],.....a[i+2^(j-1)-1],第二部分为a[i+2^(j-1)],a[i+2^(j-1)+1],..........a[i+2^j-1];二者两部分又可以表示为,f[i][j-1]f[i+2^(j-1)][j-1]因此状态转移方程可以写成\(f[i][j]=max(f[i][j-1],f[i+2^{j-1}][j-1])\) ;我们设定f[i][0]=a[i]之后就可以在O(nlogn)时间内预处理完数组。对于查询,如果要查询 l-r 区间的最大值我们需要计算出最大的x满足\(2^x<=r-l+1\) 于是,\(ans=max(f[l][x],f[r-2^x+1][r])\) ,我们便可以在O(1)下算出答案。

因为中的log函数效率不高,所以我们可以用递推的方式计算出所有可能的log值,通过log[n]=log[n/2]+1;计算即可。

例题:数列区间最大值:

问题描述:

输入一串数字,给你M个询问,每次询问给出两个数字,x和y,求出x到y区间的最大值。

输入格式:

一个整数N表示数字的个数,接下来一行为N个数。第三行读入一个数M,表示要询问的次数,接下来M行,每行两个整数x,y

样例输入:

10
3 2 4 5 6 8 1 2 9 7
2
1 4
3 8

样例输出:

5
8

题解:

/**********************************************************
* @Author:             Maple
* @Date:               2020-02-22 12:16:47
* @Last Modified by:   Maple
* @Last Modified time: 2020-02-22 13:37:09
* @Remark: 
**********************************************************/
#include <bits/stdc++.h>
#define lowbit(x) (x&(-x))
#define CSE(x,y) memset(x,y,sizeof(x))
#define INF 0x3f3f3f3f
#define Abs(x) (x>=0?x:(-x))
#define FAST ios::sync_with_stdio(false);cin.tie(0);
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll , ll> pll;

const int maxn=1e6+100;
int n,m,a[maxn],f[maxn][33],lg[maxn];

int main()
{
    #ifndef ONLINE_JUDGE
    freopen("in.in","r",stdin);
    #endif
    cin>>n;
    for(int i=1;i<=n;i++)
        scanf("%d",a+i);
    lg[0]=-1;
    for(int i=1;i<=n;i++){
        lg[i]=lg[i>>1]+1;
        f[i][0]=a[i];
    }
    for(int j=1;j<=20;j++){
        for(int i=1;i+(1<<(j-1))<=n;i++){
            f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
        }
    }
    cin>>m;
    while(m--){
        int x,y;
        scanf("%d%d",&x,&y);
        int s=lg[y-x+1];
        printf("%d\n",max(f[x][s],f[y-(1<<s)+1][s]));
    }
    return 0;
}

RMQ

原文:https://www.cnblogs.com/LeafLove/p/12345136.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!