精华内容
下载资源
问答
  • RMQ

    2020-05-23 14:32:45
    RMQ ( Range Minimum / Maximum Query ) 问题是指:对于长度为 n 的数列 A,回答若干询问 RMQ (A , i , j ) ( i , j ≤ n),返回数列A中下标在 i , j 里的最小(大)值,也就是说,RMQ问题是指求区间最值的问题。...

    【简介】

    RMQ ( Range Minimum / Maximum Query ) 问题是指:对于长度为 n 的数列 A,回答若干询问 RMQ (A , i , j ) ( i , j ≤ n),返回数列A中下标在 i , j 里的最小(大)值,也就是说,RMQ问题是指求区间最值的问题。

    关于RMQ问题,还是有很多方法来求解的(像线段树啊什么的),本篇博客主要介绍一下ST算法

    要注意的是,ST算法只适用于静态区间求最值,如果是动态的,那还是乖乖打线段树吧

     

    【基本思想】

    ST算法它的本质相当于是动态规划,下面我们以求最大值为例(最小值求法和最大值差不多)

    我们用 f [ i ][ j ] 表示以 i 为起点,连续 2^j 个数中的最大值,例如 f [ 2 ][ 2 ] 就表示第 2 个数到第 5 个数的最大值

     

    (1)预处理:

    我们用A表示原序列,由于2^{0} = 1,按照 f 数组的定义,f [ i ][ 0 ] 就等于 A[ 0 ](初始化)

    对于其他的处理,我们看下图:

    RMQ

    对于每一个 f 数组表示的序列,我们都把它拆成两部分,很明显,它的最大值就是这两部分的最大值中较大的那一个

    那么转移方程就是:f [ i ][ j ] = max { f [ i ][ j - 1 ] , f [ i + ( 1 << ( j - 1 ) ][ j - 1 ] }   ( 1 << j 是位运算,相当于2^j )

    具体的代码:

    void RMQ() {
        int i, j;
        for (i = 1; i <= n; ++i)
            f[i][0] = arr[i];
        for (j = 1; (1 << j) <= n; ++j)
            for (i = 1; i + (1 << (j - 1)) <= n; ++i)
                f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
                //这里求的是静态区间最大值,若求最小,max改成min即可
    }
    

    (2)查询:

    查询的话我还是画了一个图:

    假设要查询的区间为 [ l , r ],我们用 L 表示区间 [ l , r ] 的长度,即 L = r - l + 1,下面用 k 表示 log L

    其中查询的话,区间长度 L 不一定刚好是 2 的多少次方,又因为 log L 是向下取整,那么 2^k 就有可能小于 L,这样的话,我们就不能直接用 f [ l ][ k ] 来表示答案,不然的话会有遗漏(例如上图中的左半部分)

    正确的做法是我们就从 l 往右取 2^k 个(即 f [ l ][ k ]),从 r 往左取 2^k 个(即 f [ r - ( 1 << k ) + 1 ][ k ]),这样就能保证区间 [ l , r ] 都被访问到了,重复计算的不用担心,这是计算最值而不是求和

    那么答案 answer = max { f [ l ][ k ] , f [ r - ( 1 << k ) + 1 ][ k ] }

    具体的代码如下(Log 数组是预处理出来了的):

    int search(int l, int r){
        if(l > r) return 0;
        int k = Log[r - l + 1];
        return max(f[l][k], f[r - (1 << k) + 1][k]);
    }
    for (i = 1; i <= m; ++i) {
    		cin >> l >> r;
            ans = search(l, r);
            cout << ans << '\n';
        }
    

    (3)预处理 Log 数组:

    这里注意两点:

    1、Log 数组是向下取整

    2、Log[ i ] = Log[ i / 2 ] +1

    下面是代码:

    void GetLog() {
        int i;
        Log[1] = 0;
        for (i = 2; i <= n + 1; ++i)
            Log[i] = Log[i / 2] + 1;
    }
    

    【复杂度分析】

    其实时间复杂度看代码很容易可以分析出来

    预处理部分:j 循环是O(log n),i 循环是O(n),总共是O(n * log n)

    询问部分:每次询问的复杂度是O(1),有 q 个询问就是O(q)

     

    【例题】

    例题传送门ST表

    裸的ST模板啦,代码如下:

    #include <iostream>
    #include <algorithm>
    #include <cstdio>
    #define M 25
    #define N 100005
    using namespace std;
    int n, m, arr[N], Log[N], f[N][M];
    inline void read(int &x){
        int s=0,w=1;
        char ch=getchar();
        while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
        while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
        x = s*w;
    }
    void GetLog() {
        int i;
        Log[1] = 0;
        for (i = 2; i <= n + 1; ++i)
            Log[i] = Log[i / 2] + 1;
    }
    void RMQ() {
        int i, j;
        for (i = 1; i <= n; ++i)
            f[i][0] = arr[i];
        for (j = 1; (1 << j) <= n; ++j)
            for (i = 1; i + (1 << (j - 1)) <= n; ++i)
                f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
    }
    int search(int l, int r){
        if(l > r) return 0;
        int k = Log[r - l + 1];
        return max(f[l][k], f[r - (1 << k) + 1][k]);
    }
    int main() {
        int l, r, i, k, ans;
        read(n), read(m);
        for (i = 1; i <= n; ++i)
            read(arr[i]);
        GetLog();
        RMQ();
        for (i = 1; i <= m; ++i) {
            read(l), read(r);
            ans = search(l, r);
            cout << ans << '\n';
        }
        return 0;
    }
    
    展开全文
  • rmq

    2019-03-19 19:36:55
    rmq快速离线查询当前区间的最值。i表示从i开始第i为,j表示往后2^j次方位。 void rmq_isit(bool ok) { for(int i=1;i<=n;i++) mm[i][0]=mi[i][0]=a[i]; for(int j=1;(1<<j)<=n;j++) { for...

    rmq快速离线查询当前区间的最值。i表示从i开始第i为,j表示往后2^j次方位。

    
    void rmq_isit(bool ok)
    
    {
    
        for(int i=1;i<=n;i++)
    
            mm[i][0]=mi[i][0]=a[i];
    
        for(int j=1;(1<<j)<=n;j++)
    
        {
    
            for(int i=1;i+(1<<j)-1<=n;i++)
    
            {
    
                if(ok)
    
                    mm[i][j]=max(mm[i][j-1],mm[i+(1<<(j-1))][j-1]);
    
                else
    
                    mi[i][j]=min(mi[i][j-1],mi[i+(1<<(j-1))][j-1]);
    
            }
    
    
    
        }
    
    }
    
    

    查询代码:

    
    int rmq(int l,int r)
    
    {
    
        int k=0;
    
        while((1<<(k+1))<=r-l+1)
    
            k++;
    
        int ans1=max(mm[l][k],mm[r-(1<<k)+1][k]);
    
        int ans2=min(mi[l][k],mi[r-(1<<k)+1][k]);
    
        return ans1-ans2;
    
    }
    
    
    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 22,886
精华内容 9,154
关键字:

rmq