12.16信息学笔记——ST表

TIP：最近想先整一整数据结构，之后再整算法。

来搞ST表，它是基于倍增思想的。

首先知道它维护的是可重复贡献的区间问题。

考虑一些可以维护的问题： 区间最大值、区间最小值、区间GCD、区间按位或……

我们用区间最大值来讲解。

考虑定义f(i,j)代表区间[i,i+2^j-1]的最大值。

显然有f(i,0)=a_i。

考虑转移，由于是倍增思想，所以分成两个长度相同的小区间转移：f(i,j)=max(f(i,j-1),f(i+2^j-1,j-1))也就是说是区间[i,i+2^j-1-1]与[i+2^j-1,i+2^j-1+2^j-1-1]的最大值。

预处理完所有的状态之后，我们考虑查询。

设查询的区间为[L,R]，只需要查询f(l,l+2^k-1)与f(r-2^k+1,r)的最大值即可，此处为了包含整个区间，我们取k=log₂(r-l+1)即可。 

代码（查询区间最大值）：

#include<iostream>
#include<cstdio>
using namespace std;
const int N=1e5+10;
const int M=20;
int n,m,a[N],lg[N],st[N][M],l,r;
void ipt1(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
}
void ipt2(){
    scanf("%d%d",&l,&r);
}
void init(){
    for(int i=2;i<=n;i++) lg[i]=lg[i/2]+1;
    for(int i=1;i<=n;i++) st[i][0]=a[i];
}
void build(){
    for(int i=1;i<M;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 t=lg[r-l+1];
    return max(st[l][t],st[r-(1<<t)+1][t]);
}
int main(){
    ipt1();
    init();
    build();
    while(m--){
        ipt2();
        printf("%d\n",query(l,r));
    }
    return 0;
}