倍增求RMQ

RMQ,即区间最值查询，给定一个序列，求区间l-r的最大值、最小值。

st表求RMQ，预处理O_n*logn,查询O₁。

预处理：

void init_rmq()

{

    for(rll j=1;j<=lg[n];++j)//从当前点开始的2的j次方个点

    {

        for(rll i=1;(i+(1<<j)-1)<=n;++i)//i+(1<<j)-1不能越界

        {

            f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);//取最大值

        }

    }

}

查询：

这里l到r不一定刚好是2^j，这里要么越界，要么有重复。

我们是求最值，又不是求和，有没有重复又有什么关系呢？那我们就让他有重复的部分。

代码：

ll rmq(ll l,ll r)

{

    ll k=log(r-l+1)/log(2);//处理log

    return max(f[l][k],f[r-(1<<k)+1][k]);//这里有重合部分,但重合部分取最大值不影响最后结果(又不是求和)

}

一道简单的例题：

信息学奥赛一本通（C++版）在线评测系统 (ssoier.cn)

代码：

#include<bits/stdc++.h>

#define ll long long

#define rint register int

#define rll register long long

using namespace std;

const ll N=1e5+5;

ll n,m;

ll f[N][20];

int lg[N];

inline ll read()

{

    ll x=0;

    bool flag=false;

    char ch=getchar();

    while(ch<'0'||ch>'9')

    {

        if(ch=='-')    flag=true;

        ch=getchar();

    }

    while(ch>='0'&&ch<='9')

    {

        x=(x<<3)+(x<<1)+(ch^'0');

        ch=getchar();

    }

    return flag?~x+1:x;

}

void init_rmq()

{

    for(rll j=1;j<=lg[n];++j)//从当前点开始的2的j次方个点

    {

        for(rll i=1;(i+(1<<j)-1)<=n;++i)//i+(1<<j)-1不能越界

        {

            f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);//取最大值

        }

    }

}

ll rmq(ll l,ll r)

{

    ll k=log(r-l+1)/log(2);//处理log

    return max(f[l][k],f[r-(1<<k)+1][k]);//这里有重合部分,但重合部分取最大值不影响最后结果(又不是求和)

}

int main()

{

    n=read(),m=read();//n 点的个数 m 操作数

    for(rll i=1;i<=n;++i)

    {

        f[i][0]=read();//读入数据

    }

    for(rint i=1;i<=n;++i)

    {

        lg[i]=lg[i-1]+(1<<lg[i-1]==i);//处理log

    }

    init_rmq();//初始化

    for(rll l,r,i=1;i<=m;++i)

    {

        l=read(),r=read();

        printf("%lld\n",rmq(l,r));//查询

    }

    return 0;

}

巴特西

倍增求RMQ

最新文章

热门文章