RMQ问题_ST表总结 | Llf0703's blog

RMQ问题_ST表总结

Llf0703 4月 09, 2018

RMQ问题

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

ST表

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

ST表查询问题包含初始化和查询操作，其中初始化的时间复杂度为O(n*logn)，查询的时间复杂度仅为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;
}

RMQ问题

ST表

初始化

起始状态

状态转移

查询

模板题

相关例题