RMQ算法分析

我就是我 2022-08-10 17:30 163阅读 0赞

RMQ算法，是一个快速求区间最值的离线算法，预处理时间复杂度O（n\*log(n)），查询O(1)，所以是一个很快速的算法，当然这个问题用线段树同样能够解决。

问题：给出n个数ai，让你快速查询某个区间的的最值。

算法分类：DP+位运算

算法分析：这个算法就是基于DP和位运算符，我们用dp【i】【j】表示从第 i 位开始，到第 i + 2^j -1 位的最大值或者最小值。

那么我求dp【i】【j】的时候可以把它分成两部分，第一部分从 i 到 i + 2 ^( j-1 ) - 1 ，第二部分从 i + 2 ^( j-1 ) 到 i + 2^j - 1 次方，其实我们知道二进制数后一个是前一个的二倍，那么可以把 i --- i + 2^j 这个区间 通过2^(j-1) 分成相等的两部分， 那么转移方程很容易就写出来了。

转移方程： **mm \[ i \] \[ j \] = max ( mm \[ i \] \[ j - 1 \] , mm \[ i + ( 1 << ( j - 1 ) ) \] \[ j - 1 \] );**

代码：

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

那么查询的时候对于任意一个区间 l -- r ，我们同样可以得到区间差值 len = （r - l + 1）。

那么我们这一用小于2^k<=len，的 k 把区间分成可以交叉的两部分l 到 l+2^（k）- 1, 到 r -(1<<k)+1 到 r 的两部分，很easy的求解了。

查询代码：

int rmq(int l,int r)
    {
        int k=0;
        while((1<<(k+1))<=r-l+1)
            k++;
        //printf("%d %d %d %d\n",l,l+(1<<k),r-(1<<k)+1,r-(1<<k)+1+(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;
    }

顺便写一道练习题目： [poj 3264 **Balanced Lineup**][poj 3264 _Balanced Lineup]

求区间差值，那么很简单一个应用。

[poj 3264 _Balanced Lineup]: http://poj.org/problem?id=3264