ST表

2022/8/15 ST表倍增区间最值

预处理区间最值O(nlogn)

查询O(1)

对于一组长度为N的队列，进行M次询问，每次询问一个区间，查找该区间内的最大数值

如果用暴力枚举的话，时间复杂度最坏能到O(NNM)，当数据量大时肯定会TLE

ST表是一种预处理复杂度为O(logn)，查询复杂度为O(1)的一种查区间最值的方法，但是这种方法有缺陷，仅限于数据元素不变的静态表，当数据元素会实时发生变化时并不适用（用线段树解决动态区间最值问题，蒻苟还没学线段树，不会这个）

ST表，预处理二维数组 st [ i ][ j ]，其中表示数组中第 i 位置开始 2^j 个位置内的最值，所以对于int类型，j的范围就在30以下，该预处理二维数组的大小还是挺小的。

有点类似倍增，我们发现 st [ 3 ][ 2 ] 可以将2分成两个1，就是把2^2分成了2^1的两个部分，用 max ( st [ 3 ][ 1 ]，st [ 5 ][ 1 ] ) 两个部分来表示 st [ 3 ][ 2 ] 的区间最大值。

查询的时候先计算出查询区间的长度(我们需要找到一个最大的k满足2^k<=len)，因为不能保证区间长度是2的次方，所以我们需要在区间内找到一个x值，使得 x + 2^k -1= r，因此

x=r-2^k+1 ，我们只需要查询 max ( st [ l ][ m ] ，st [ r - ( 1<<m ) + 1 ][ m ] ))即可

#include <bits/stdc++.h>
#define rep(i,n,m) for(int i=n;i<=m;++i)
#define per(i,n,m) for(int i=n;i>=m;--i)
using namespace std;
const int N=2e6+10;
int st[N][30];
//这个区间是左闭右开 是[N,N+2^30)
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);
    int n,q;cin>>n>>q;
    rep(i,1,n)cin>>st[i][0]; 第i个位置到i+2^0位置的最值，[i,i+2^0)，左闭右开 
    rep(j,1,30){  //枚举区间的长度，从 2^0 → 2^30
        for(int i=1;i+(1<<j)-1<=n;++i){   //
           //防止数组值越界，因此区间右值不能超过数组右端点 i+(1<<j)-1
            st[i][j]=max(st[i][j-1],st[i+(1<<j-1)][j-1]);
        }
    }
    while (q--) {
        int l,r;cin>>l>>r;
        int m=log(r-l+1)/log(2);
        //l到r之间的长度大小（2的次方）
        cout<<max(st[l][m],st[r-(1<<m)+1][m]))<<'\n';
    }
    return 0;
}

当然，也可以用ST表查询最小值，静态区间最值问题都可以解决，要抓紧时间学学线段树了，马上就大二了。。。

附上洛谷题目：
P3865 【模板】ST 表 - 洛谷 | 计算机科学教育新生态

LOADING

ST表