浅谈ST表

雨点打透心脏的1/2处 2021-11-05 12:24 262阅读 0赞

咱们先来**前情引导**一下

假如你的面前有一个区间【1，6，2，8，7，4，6，3，9，3，0】请问，这个区间的最大值是森魔？最小值是森魔？**（千万别说你不知道）**

答案显然：max值是9，min值是0。这种问题往往被我们RMQ ( Range Minimum / Maximum Query ) 问题，是指：对于长度为 n 的数列 A，回答若干询问 RMQ (A , i , j ) ( i , j ≤ n)，返回数列A中下标在 i , j 里的最小（大）值，也就是说，RMQ问题是指求区间最值的问题。

现在把自己想象成一个什么也不懂的孩子，假如你一眼看不出来这个区间的最值，你会怎样寻找它？

第一种想法，从左到右做两个指针i，j，从左到右暴力枚举。遇见大的（举例）就更新，不然就跳过。这种暴力算法的时间复杂度是O(n)-O(n)的

第二种想法，利用线段树（一种强大的数据结构）进行区间查询，其时间复杂度为O(n)-O(logn)。

但是，如果还没有学过线段树算法，也不想用暴力。那么我们的ST表就要登场啦。

**算法介绍**

ST表这个算法，其功能很单调，主要就是用于求解区间RMQ问题（但是请注意ST表**只能用于静态查询**，如果题目中是动态的RMQ还是推荐线段树），它可以做到O（nlogn）的预处理，O（1）的查询，可以说很强大了。

ST表的思想是基于动态规划的，下面以求一段区间的最大值为例子。

我们用f\[i\]\[j\]表示以i为起点，连续的2^j个数中的最大值（左闭右开），f\[1\]\[3\]表示从1到8的最大值。

（1）第一步：预处理出f数组

首先，由于20=1。所以f\[i\]\[0\]就是这个区间的左端，对于f区间，我们不断的对其倍增，使其区间不断扩大，可以得到如下的式子。

f \[ i \]\[ j \] = max \{ f \[ i \]\[ j - 1 \] , f \[ i + ( 1 << ( j - 1 ) \]\[ j - 1 \] \}（因为我们要求的是最大值嘛每一个j都是由上一个j求过来的，i+（1<<(j-1)）就表示两个区间的分开点）

（2）第二步：把log数组处理出来

这是在代码中的顺序，在理解时先看第三步

log\[i\]=log\[i/2\]+1(需要向下取整)

（3）第三步：进行查询

假设要查询的区间为 \[ l , r \]，我们用 L 表示区间 \[ l , r \] 的长度，即 L = r - l + 1，下面用 k 表示 logL。

其中查询的话，区间长度 L 不一定刚好是 2 的多少次方，又因为 logL 是向下取整，那么 2^k 就有可能小于 L，这样的话，我们就不能直接用 f \[ l \]\[ k \] 来表示答案，不然的话会有遗漏。

正确的做法是我们就从 l 往右取 2^k 个（即 f \[ l \]\[ k \]），从 r 往左取 2^k 个（即 f \[ r - ( 1 << k ) + 1 \]\[ k \]），这样就能保证区间 \[ l , r \] 都被访问到了，重复计算的不用担心，这是计算最值而不是求和

那么答案 answer = max \{ f \[ l \]\[ k \] , f \[ r - ( 1 << k ) + 1 \]\[ k \] \}

**代码实现**

1 #include<iostream>
     2 #include<cstdio>
     3 #include<algorithm>
     4 #include<cstring>
     5 #include<cmath>
     6 using namespace std;
     7 const int MAXN=1e6+10;
     8 int maxn[MAXN][21];
     9 int m,n;
    10 int ask(int l,int r)
    11 {
    12     int k=log2(r-l+1);
    13     return max(maxn[l][k],maxn[r-(1<<k)+1][k]);
    14 }
    15 int main()
    16 {
    17     scanf("%d%d",&n,&m);
    18     for(int i=1;i<=n;i++)
    19     {
    20         scanf("%d",&maxn[i][0]);
    21     }
    22     
    23     for(int j=1;j<=21;j++)
    24         for(int i=1;i+(1<<j)-1<=n;i++)
    25         {
    26             maxn[i][j]=max(maxn[i][j-1],maxn[i+(1<<(j-1))][j-1]);
    27         } 
    28             
    29     for(int i=1;i<=m;i++)
    30     {
    31         int l,r;
    32         scanf("%d%d",&l,&r);
    33         printf("%d\n",ask(l,r));
    34     }
    35     return 0;
    36 }

嗯，就是这样了，谢谢各位！

多多帮助蒟蒻宣传一下博客哦！

转载于:https://www.cnblogs.com/mo-qian/p/11291330.html