ST表

￡神魔★判官ぃ 2022-05-28 07:25 157阅读 0赞

**转载博主:[点这里][Link 1]**

ST表学习   
作用：ST算法是用来求解给定区间RMQ的最值，本文以最小值为例

举例：

给出一数组A\[0~5\] = \{5,4,6,10,1,12\},则区间\[2,5\]之间的最值为1。

方法：ST算法分成两部分：离线预处理 （nlogn）和 在线查询（O(1)）。虽然还可以使用线段树、树状链表等求解区间最值，但是ST算法要比它们更快，而且适用于在线查询。

（1）离线预处理：运用DP思想，用于求解区间最值，并保存到一个二维数组中。

（2）在线查询：对给定区间进行分割，借助该二维数组求最值

具体解释：

（1）离线预处理：

ST算法使用DP思想求解区间最值，貌似属于区间动态规划，不过区间在增加时，每次并不是增加一个长度，而是使用倍增的思想，每次增加2^i个长度。

使用F\[i,j\]表示以i为起点，区间长度为2^j的区间最值，此时区间为\[i,i + 2^j - 1\]。

比如，F\[0,2\]表示区间\[0,3\]的最小值，即等于4，F\[2,2\]表示区间\[2,5\]的最小值，即等于1。

在求解F\[i,j\]时，ST算法是先对长度为2^j的区间\[i,i + 2^j - 1\]分成两等份，每份长度均为2^(j - 1)。之后在分别求解这两个区间的最值F\[i,j - 1\]和F\[i + 2^(j - 1),j - 1\]。，最后在结合这两个区间的最值，求出整个区间的最值。特殊情况，当j = 0时，区间长度等于1，即区间中只有一个元素，此时F\[i,0\]应等于每一个元素的值。

举例：要求解F\[1,2\]的值，即求解区间\[1,4\] = \{4,6,10,1\}的最小值，此时需要把这个区间分成两个等长的区间，即为\[1,2\]和\[3,4\]，之后分别求解这两个区间的最小值。此时这两个区间最小值分别对应着F\[1,1\] 和 F\[3,1\]的值。

状态转移方程是 F\[i,j\] = min(F\[i,j - 1\],F\[i + 2^(j - 1),j - 1\])

初始状态为：F\[i,0\] = A\[i\]。

在根据状态转移方程递推时，是对每一元素，先求区间长度为1的区间最值，之后再求区间长度为2的区间最值，之后再求区间长度为4的区间最值….，最后，对每一个元素，在求解区间长度为log2^n的区间最值后，算法结束，其中n表示元素个数。

即：先求F\[0\]\[1\]，F\[1\]\[1\]，F\[2\]\[1\]，F\[3\]\[1\]，,，F\[n\]\[1\]，再求.F\[0\]\[2\]，F\[1\]\[2\]，F\[2\]\[2\]，F\[3\]\[2\]，,，F\[m\]\[2\]，… 。

（2）在线处理：这里我们是已知待查询的区间\[x,y\]，求解其最值。

在预处理期间，每一个状态对应的区间长度都为2^i。由于给出的待查询区间长度不一定恰好为2^i，因此我们应对待查询的区间进行处理。

这里我们把待查询的区间分成两个小区间，这两个小区间满足两个条件：（1）这两个小区间要能覆盖整个区间（2）为了利用预处理的结果，要求小区间长度相等且都为2^i。注意两个小区间可能重叠。

如：待查询的区间为\[3,11\]，先尽量等分两个区间，则先设置为\[3,7\]和\[8,11\]。之后再扩大这两个区间，让其长度都等于为2^i。刚划分的两个区间长度分别为5和4，之后继续增加区间长度，直到其成为2^i。此时满足两个条件的最小区间长度为8,此时i = 3。

在程序计算求解区间长度时，并没有那么麻烦，我们可以直接得到i，即等于直接对区间长度取以2为底的对数。这里，对于区间\[3,11\]，其分解的区间长度为int（log(11 - 3 + 1)） = 3，这里log是以2为底的。

根据上述思想，可以把待查询区间\[x，y\]分成两个小区间\[x，x + 2^i - 1\] 和 \[y - 2^i + 1，y\] ，其又分别对应着F\[x,i\]和F\[y - 2^i + 1,i\]，此时为了求解整个区间的最小值，我们只需求这两个值得最小值即可，此时复杂度是O(1)。

代码如下:

#include<algorithm>
    #include<iostream>
    #include<cstdlib>
    #include<cstring>
    #include<cstdio>
    #include<cmath>
    #include<queue>
    using namespace std;
    
    #define N 2000
    
    int stmax[N][20],stmin[N][20],mn[N];
    int a[N];
    
    int t,q,n;
    int x,y;
    
    void init()
    {
        mn[0]=-1;
        for (int i=1;i<=n;i++)
        {
            mn[i]=((i & (i-1))==0) ? mn[i-1]+1 : mn[i-1];//可以是log((double)i)/log(2 .0)
            stmax[i][0]=stmin[i][0]=a[i];
        }
        for (int j=1;j<=mn[n];j++)
            for (int i=1;i+(1<<j)-1<=n;i++)
            {
                stmax[i][j]=max(stmax[i][j-1],stmax[i+(1<<(j-1))][j-1]);
                stmin[i][j]=min(stmin[i][j-1],stmin[i+(1<<(j-1))][j-1]);
            }
    }
    
    int rmq_max(int L,int R)
    {
        int k=mn[R-L+1];
        return max(stmax[L][k],stmax[R-(1<<k)+1][k]);
    }
    
    int rmq_min(int L,int R)
    {
        int k=mn[R-L+1];
        return min(stmin[L][k],stmin[R-(1<<k)+1][k]);
    }
    
    int main()
    {
        scanf("%d",&t);
        while (t--)
        {
            scanf("%d",&n);
            for (int i=1;i<=n;i++)
                scanf("%d",&a[i]);
            init();
            scanf("%d",&q);
            while (q--)
            {
                scanf("%d%d",&x,&y);
                printf("%d %d\n",rmq_max(x,y),rmq_min(x,y));
            }
        }
        return 0;
    }

[Link 1]: https://blog.csdn.net/whistlena/article/details/52191463#reply