LOADING

加载过慢请开启缓存 浏览器默认开启

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 表 - 洛谷 | 计算机科学教育新生态