ST表讲解_牛客博客

ST表主要用于解决RMQ问题（区间最值问题）
当然你可以用线段树等，但今天用一种ST表（倍增算法）

ST表是倍增算法的一个典型应用
暴力做RMQ问题，往往会超时，ST表利用对其进行优化

给定一段序列A，ST算法能在O(NlogN)的时间预处理后，以O(1) 的复杂度查询，在线回答在一段区间l,r 中最大（小）值是多少。

f[i][j]用于表示在序列a中，从第i位数字往后数2^j个数，这个区间内的最大值，即区间[ i , i + 2 ^j ]内取得的最大值。

而这段区域的最大值等于左右子区间的最大值,2^j = 2 * 2 ^j-1 = 2^j-1 + 2^j-1,把区间[i,i+2^j]分成[i , i + 2^j-1 ] [ i + 2^j-1 + 1,2^j]
(即f [ i ] [ j - 1 ] 与 f [ i + 2 ^j-1 - 1 ] [ j -1 ] ）

我们可得：F [ i ] [ j ] = max ( F [ i ] [ j - 1 ] , F [ i + 2 ^j-1 - 1 ] [ j - 1 ] )
递推边界为f[i][0]=a[i]

其实说白了就是：相求大区间就先求出小区间，求小区间就求小小区间，一直这样套娃到最低层。

但是我们查询的区间不一定总是2的倍数，也有可能会超出区间
所以我们询问区间[l,r]时要用一个k，k=log₂(len)，len为区间的长度，k向下取整
len=r-l+1
2^t<len<2^t+1
左右区间最大值分别是F [ l , k ] 与F [ r - 2^k + 1 , k ]

#include<cstdio>
#include<iostream>
#include<cmath>

using namespace std;

long f[100001][40];
int n,m;

void ST()//预处理
{
   
    for(int k=1;k<=(int)log2(n);k++){
   
        for(int i=1;i<=n-(1<<k)+1;i++){
   
            f[i][k]=max(f[i][k-1],f[i+(1<<(k-1))][k-1]);
        }
    }
}
int query(int l,int r)//查询
{
   
        int k=log2(r-l+1);
        return max(f[l][k],f[r-(1<<k)+1][k]);

}
int a[100];
int main(){
   
    cin>>n>>m;
    
    int temp;
    for(int i=1;i<=n;i++){
   
        scanf("%d",&a[i]);
        
        f[i][0]=a[i];
    }

    int l,r;
    for(int i=1;i<=m;i++){
   
    scanf("%d%d",&l,&r);
    cout<<query(l,r);
    }
	
    return 0;
}