RMQ问题_ST表总结

@Llf  April 9, 2018

RMQ问题

RMQ问题是指多次询问一个区间中最小或最大值的问题。但是因为不包括修改,只涉及离线操作,所以线段树或者树状数组显得有一些多余了。而且数列中的元素个数可能非常大,像线段树开四倍空间肯定是要MLE的。这里介绍一种高效的ST表来解决这种问题。

ST表

我的理解:ST表运用动态规划和二分的思想来完成。

ST表查询问题包含初始化和查询操作,其中初始化的时间复杂度为$O(n\times \log n)$,查询的时间复杂度仅为$O(1)$。

初始化

初始化主要运用动态规划来完成。

我们将原来的数列用a[]储存,同时定义一个二维的f[][]数组,f[i][j]表示从第i个数起连续2^j个数中的最值,即储存[i,i+2^j-1]中的最值。然后我们就可以使用f数组进行动态规划。

起始状态

我们知道2^0=1,所以当j=0时,f[i][j]其实储存的就是第i项的值,这就成了我们初始化的依据。初始化可以这么写:

for (int i=1;i<=n;i++) f[i][0]=a[i];

状态转移

前面已经说过,这个状态转移的实质就是二分。在这里,我们将[i,i+2^j-1]二分为[i,i+2^(j-1)-1][i+2^(j-1),i+2^j-1]。因为每个区间中的项数在j!=0时一定是偶数,所以这样一定能分为两段项数相同的区间。于是我们得到了状态转移方程f[i, j]=max(f[i,j-1], f[i+2^(j-1),j-1])。状态转移可以这么写:

for (int j=1;(1 << j)<=n;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]);

其中1<<j就是2^j

但是为什么j要写在外层循环呢?

因为这个状态转移的实质是:先更新所有长度为f[i][0]即1个元素,然后通过2个1个元素的最值,获得所有长度为f[i][1]即2个元素的最值,然后再通过2个2个元素的最值,获得所有长度为f[i][2]即4个元素的最值,以此类推更新所有长度的最值。

而如果是i在外,j在内的话,我们更新的顺序就是f[1][0],f[1][1],f[1][2],f[1][3]表示更新从1开始1个元素,2个元素,4个元素,8个元素的最值,这里f[1][3]=min(min(a[0],a[1],a[2],a[3]),min(a[4],a[5],a[6],a[7]))的值,但是我们根本没有计算min(a[0],a[1],a[2],a[3])min(a[4],a[5],a[6],a[7]),所以这样的方法肯定是错误的。

所以初始化就这么写:

void st(int n)
{
    for (int i=1;i<=n;i++) f[i][0]=a[i];
    for (int j=1;(1 << j)<=n;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]);
}

查询

对于查询[l,r]这个区间中的最值,我们也可以将其分为两部分,再分别取两部分的最值来得到整个区间的最值。

我们取一个值k=log2(r-l+1),并将k作为二分的中点,将[l,r]这个区间分为[l,k][r-2^k+1,k]这两段。可以很显然的发现,这两段是有重复的,但是对结果没有任何影响。

查询可以这么写:

inline int query(int l,int r)
{
    int k=log2(r-l+1);
    return max(f[l][k],f[r-(1 << k)+1][k]);
}

模板题

洛谷P3865 【模板】ST表为例

#include<bits/stdc++.h>
using namespace std;
int a[100005];
int f[100005][20];
int n,m,b,c;
void st(int n)
{
    for (int i=1;i<=n;i++) f[i][0]=a[i];
    for (int j=1;(1 << j)<=n;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]);
}
inline int query(int l,int r)
{
    int k=log2(r-l+1);
    return max(f[l][k],f[r-(1 << k)+1][k]);
}
int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++) cin>>a[i];
    st(n);
    for (int i=1;i<=m;i++)
    {
        scanf("%d%d",&b,&c);
        printf("%d\n",query(b,c));
    }
    return 0;
}

相关例题

待更新。。。


添加新评论