【模板】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;
    }
}