[C++知识库]关于ST表的建立与查询(板子)

关于ST表的建立与查询(板子)

题目描述：

输入一串数字，给你M个询问，每次询问就给你两个数字 X,Y，要求你说出X到Y这段区间内的最大数。

输入：

第一行两个整数 N,M 表示数字的个数和要询问的次数；

接下来一行为 N 个数；

接下来 M 行，每行都有两个整数 X,Y。

输出：

输出共 M 行，每行输出一个数。

输入样例：

10 2
3 2 4 5 6 8 1 2 9 7
1 4
3 8

输出样例：

5
8

Tip：
对于全部数据，$1$$\le$$N$$\le$$1e5$,$1$$\le$$M$$\le$$1e6$,$1$$\le$$X$$\le$$Y$$\le$$N$。

思路： 显然直接暴力即使预处理再查询时间复杂度也来到$1e10$级别。预处理每一段的$max$这时候就可以使用ST表。

ST表主要有两个操作：
$1:$以$O(nlogn)$级别的复杂度预处理所有$2$的次方长度的区间。
2:之后的每一次查询的区间都可以通过:$max(st[L][k],st[R?(1<<k)+1][k])$来获得。$st$数组的第一维表示以哪个坐标为起点，$k$表示是总长度为$2^k$的区间。

核心代码：
$1:make$_$st()$

void make_st(){
    int k=__lg(n);
    for(int i=1;i<=n;i++)st[i][0]=a[i];
    for(int i=1;i<=k;i++){
        for(int j=1;j+(1<<i)-1<=n;j++){
            st[j][i]=max(st[j][i-1],st[j+(1<<(i-1))][i-1]);
        }
    }
}

$2:int$ $query($$int$ $l,int$ $r)$

int query(int l,int r){
    int k=__lg(r-l+1);
    return max(st[l][k],st[r-(1<<k)+1][k]);
}

• 本题参考代码：

#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define int long long 
#define re register int
#define pb emplace_back
#define lowbit(x) (x&-x)
#define fer(i,a,b) for(re i = a ; i <= b ; i ++)
#define der(i,a,b) for(re i = a ; i >= b ; i --)
#define snow ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
typedef pair<int,int>PII;
typedef pair<int,string>PIS;
int n,m;
const int N=2e5+10;
int a[N];
int st[N][20];
void make_st(){
    int k=__lg(n);
    for(int i=1;i<=n;i++)st[i][0]=a[i];
    for(int i=1;i<=k;i++){
        for(int j=1;j+(1<<i)-1<=n;j++){
            st[j][i]=max(st[j][i-1],st[j+(1<<(i-1))][i-1]);
        }
    }
}
int query(int l,int r){
    int k=__lg(r-l+1);
    return max(st[l][k],st[r-(1<<k)+1][k]);
}
signed main(){
    snow;
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i];
    make_st();
    while(m--){
        int l,r;
        cin>>l>>r;
        cout<<query(l,r)<<endl;
    }
    return 0;
}