ST表[学习笔记]

只看该作者 · 2021-2-20 23:07

二维ST表,一维ST表。
概念
ST表是用来求解区间最大值的一种优秀的离线算法，它可以 O ( n l o g n ) O(nlogn)O(nlogn)预处理，，然后O(1)查询，如何实现呢？

只看该作者 · 2021-2-20 23:08

思想
运用了近似于区间DP的方法，一个大区间有小区间转移得到，不同的是，我们定义S T [ i ] [ k ] ST[i][k]ST[i][k]表示从第i ii个位置起，2 k 2^k2
k
个数的最大值，咋转移呢？发现我们只处理2 k 2^k2
k
所以2 k 2^k2
k
可以拆成两个没有相交的长度为2 k − 1 2^{k-1}2
k−1
的区间
分别是S T [ i ] [ k − 1 ] ST[i][k-1]ST[i][k−1]和S T [ i + 2 k − 1 ] [ i − 1 ] ST[i+2^{k-1}][i-1]ST[i+2
k−1
][i−1]，也就是说我们需要先预处理这两个小区间的值，而这两个小区间需要更小的区间来更新，所以到底层就是S T [ i ] [ 0 ] ST[i][0]ST[i][0]也就是每个位置上的原数了，然后再一层一层的向上贡献，至此实现方法已经有了

只看该作者 · 2021-2-20 23:08

实现

复制

//预处理

inline void pre()

{

        for (int i=1;i<=e;i++)

        for (int k=1;k<=n-(1<<i)+1;k++)

        f[k][i]=max(f[k][i-1],f[k+(1<<(i-1))][i-1]);

        return ;

}

只看该作者 · 2021-2-20 23:13

我们外层枚举2k
，内层循环每个位置，然后每次拆成上面两个式子的max就好了

只看该作者 · 2021-2-20 23:14

复制

//询问

inline int que(int l,int r)

{

        int t=(log2(r-l+1));

        return max(f[l][t],f[r-(1<<t)+1][t]);

}

只看该作者 · 2021-2-20 23:15

发现询问区间有两种情况
1. 1.1.是2 k 2^k2
k
，那么直接对区间长取个l o g 2 ( r − l + 1 ) log_2({r-l+1})log
2

(r−l+1)然后输出S T [ l ] l o g ] ST[l]log]ST[l]log]就行了
2. 2.2.不是2 k 2^k2
k
，那么不难发现，他可以拆成两个2 k < l e n 2^k<len2
k
<len的区间的并，也就是说从区间左端点向右一段不超过区间长，但大于1 2 l e n \frac{1}{2}len
2
1

len的区间，从右端点向左一段不超过区间长，但大于1 2 l e n \frac{1}{2}len
2
1

len的区间，发现都过了1 2 \frac{1}{2}
2
1

所以肯定会有交集，也肯定将整个区间覆盖全了，然后直接对这两部分取max就好
然后我们发现，len是2 k 2^k2
k
就会分成两个完全覆盖区间的相同的区间，所以就可以合并这两种情况了，输出上面代码里的式子就好了

只看该作者 · 2021-2-20 23:16

只看该作者 · 2021-2-20 23:18

实现：

复制

//预处理

inline void pre()

{

        int t=log2(n),e=log2(m);

        for (int i=0;i<=t;i++)

        for (int k=0;k<=e;k++)

        {

                if (i==0&&k==0) continue;

                for (int j=1;j<=n-(1<<i)+1;j++)

                for (int p=1;p<=m-(1<<k)+1;p++)

                if (i==0)

                f[j][p][i][k]=max(f[j][p][i][k-1],f[j][p+(1<<(k-1))][i][k-1]);

                else 

                f[j][p][i][k]=max(f[j][p][i-1][k],f[j+(1<<(i-1))][p][i-1][k]);

        }

        return ;

}

只看该作者 · 2021-2-20 23:19

自己意会一下分割方式，脑补一下过程[

只看该作者 · 2021-2-20 23:20

复制

//查询

inline int que(int x,int y,int l,int r)

{

        int t=log2(l-x+1);

        int e=log2(r-y+1);

        int a1=max(f[x][y][t][e],f[l-(1<<t)+1][r-(1<<e)+1][t][e]);

        int a2=max(f[l-(1<<t)+1][y][t][e],f[x][r-(1<<e)+1][t][e]);

        return max(a1,a2);

}

只看该作者 · 2021-2-20 23:21

这也是个神奇的过程，继续脑补

需要了解的是
若需要在线，可以用树状数组或者线段树
二维ST表还有另一种写法，可以少一个log，具体实现就是S T [ i ] [ j ] [ k ] ST[i][j][k]ST[i][j][k]表示以( i , j ) (i,j)(i,j)为起点2 k 2^k2
k
为边长的正方形的最大值，询问需要费点时间，可以被一个宽度极小的矩形卡死，看实际情况吧

只看该作者 · 2021-2-20 23:23

一维完整代码

复制

//By AcerMo

#include<cmath>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

const int M=100500;

int n,m,e,f[M][20];

inline void read(int &x)

{

        x=0;char ch=getchar();

        while (!isdigit(ch)) ch=getchar();

        while (isdigit(ch)) x=x*10+ch-'0',ch=getchar();

        return ;

}

inline void write(int x)

{

        if (x>9) write(x/10);

        putchar(x%10+'0');

        return ;

}

inline void pre()

{

        for (int i=1;i<=e;i++)

        for (int k=1;k<=n-(1<<i)+1;k++)

        f[k][i]=max(f[k][i-1],f[k+(1<<(i-1))][i-1]);

        return ;

}

inline int que(int l,int r)

{

        int t=(log2(r-l+1));

        return max(f[l][t],f[r-(1<<t)+1][t]);

}

signed main()

{

        read(n);read(m);e=log2(n);

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

        read(f[i][0]);pre();

        for (int i=1;i<=m;i++)

        {

                int l;read(l);

                int r;read(r);

                write(que(l,r));puts("");

        }

        return 0;

}

只看该作者 · 2021-2-20 23:25

二维完整代码

复制

//By AcerMo

#include<cmath>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

const int M=305;

int n,m,q;

int f[M][M][10][10];

inline void read(int &x)

{

        x=0;char ch=getchar();

        while (!isdigit(ch)) ch=getchar();

        while (isdigit(ch)) x=x*10+ch-'0',ch=getchar();

        return ;

}

inline void write(int x)

{

        if (x>9) write(x/10);

        putchar(x%10+'0');

        return ;

}

inline void pre()

{

        int t=log2(n),e=log2(m);

        for (int i=0;i<=t;i++)

        for (int k=0;k<=e;k++)

        {

                if (i==0&&k==0) continue;

                for (int j=1;j<=n-(1<<i)+1;j++)

                for (int p=1;p<=m-(1<<k)+1;p++)

                if (i==0)

                f[j][p][i][k]=max(f[j][p][i][k-1],f[j][p+(1<<(k-1))][i][k-1]);

                else 

                f[j][p][i][k]=max(f[j][p][i-1][k],f[j+(1<<(i-1))][p][i-1][k]);

        }

        return ;

}

inline int que(int x,int y,int l,int r)

{

        int t=log2(l-x+1);

        int e=log2(r-y+1);

        int a1=max(f[x][y][t][e],f[l-(1<<t)+1][r-(1<<e)+1][t][e]);

        int a2=max(f[l-(1<<t)+1][y][t][e],f[x][r-(1<<e)+1][t][e]);

        return max(a1,a2);

}

signed main()

{

        read(n);read(m);

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

        for (int k=1;k<=m;k++)

        read(f[i][k][0][0]);

        pre();read(q);

        while (q--)

        {

                int x,y;read(x),read(y);

                int l,r;read(l),read(r);

                write(que(x,y,l,r));puts("");

        }

        return 0;

}