【模板】ST表图解

· · 题解

翻了很多题解没找到一篇详细图解,于是就有了这篇。

定义啥的其他题解都有,就不赘述了,我们直接结合图例来理解代码。 - ## 预处理阶段。 1. 首先你应该知道的是,ST表是利用倍增思想来缩短时间的。而倍增就体现在他数组的定义中:对于$f[i][j]$,指的是在序列的第i项,**向后$2^j$个元素所包含序列间的最大值**。 对于$i=1$,我们可以画出这么一个图,其下标即为$j$: ![](https://cdn.luogu.com.cn/upload/image_hosting/digxpwj5.png) 那么对于当前$i$转移其实很明显了,我们可以直接考虑将两个小区间的答案合并,即为这个大区间的值;如图中$f[1][2]$即可由$max(f[1][1],f[3][1])$转移来。 $$f[i][j]=max(f[i][j-1],f[i+2^{j-1}][j-1])$$ **其中$2^{j-1}$也可写为$(1<<(j-1))$**,这里位运算会更方便也会更快。 这个式子告诉我们,ST表类似于区间DP,是由两个小区间合并上来的。**所以应该先枚举区间长度l(这里即为$j$),再枚举$i$.** 2. 然后一个问题应运而生了:我们这个转移方程有没有**边界**呢? 不妨来看一下$i=6$的图: ![](https://cdn.luogu.com.cn/upload/image_hosting/75ybmzf5.png) 可以看出在$i=6$时,$j=3$的范围是$[6,13(6+2^3)]$,已经超出了我们数据的范畴。所以当$j=3$时,$i$只能取到$[1,5(12-2^3+1)]

由上例再根据转移方程,不难看出当j确定时,i的范围受限在[1,n-2^j+1]

那么又根据i=1的情况,可知j应满足:

最终附上预处理代码: ```cpp scanf("%d%d",&n,&m); lg[1]=0; for (int i=2;i<=n;i++) lg[i]=lg[i>>1]+1; //求lg[i]函数。 for (int i=1;i<=n;i++) scanf("%d",&f[i][0]); for (int j=1;j<=lg[n];j++) for (int i=1;i<=n-(1<<j)+1;i++){ //注意两个边界 f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]); } ``` 时间复杂度为$O(N·logN)

我们现在来求红色标记区间[L,R]的最值。如果要最大化利用ST表,仍应该考虑类似处理ST表的方法,将该区间分成 两个ST表可直接维护的小区间,然后二者求最值即可。

于是对于起始点点在ST表里的取值即为:$f[L][k]

但是我们应该如何确定该子区间的起点呢?由于子区间长度为2^k,设起点在D处,则满足:

(D+2^k-1=R) \Leftrightarrow (D=R-2^k+1)

于是对于终止点在ST表里的取值即为:f[D][k],可证明这样一定可以覆盖整个区间。

综上,对于区间[L,R]求其最值,不难发现答案即为:

\max(f[L][k],f[R-(1<<k)+1][k])

接下来是一个例子:

对于蓝色区间,我们先找到k=lg[8-2+1]=lg[7]=2,则两个子区间即为:[2,5],[5,8],对应了f[2][2],f[5][2],两个取最值即可。

附上求值部分代码:

    for (int i=1;i<=m;i++)
    {
        cin>>x>>y; int l=lg[y-x+1];
        cout<<max(f[x][l],f[y-(1<<l)+1][l])<<endl;
    }

虽说是详细图解,但好像更偏向于一些简单的数学证明。。

ST表对于RMQ问题还是有很大的使用空间,希望各位能好好掌握。

最后附上我丑陋的代码:

#include <iostream>
using  namespace std;

int n,m,x,y,a[100010],lg[100010],f[100010][20];

int main()
{
    cin>>n>>m; lg[1]=0;
    for (int i=2;i<=n;i++) lg[i]=lg[i>>1]+1;
    for (int i=1;i<=n;i++) cin>>f[i][0];
    for (int j=1;j<=lg[n];j++)
    for (int i=1;i<=n-(1<<j)+1;i++){
        f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
    }

    for (int i=1;i<=m;i++)
    {
        cin>>x>>y; int l=lg[y-x+1];
        cout<<max(f[x][l],f[y-(1<<l)+1][l])<<endl;
    }
}