ST表模板

Expert_Dream · 2023-07-28 12:42:56 · 个人记录

ST表

ST表

ST表一般处理：给定 n 个数，有 m 个询问，对于每个询问，你需要回答区间 [l,r] 中的最大值。

设：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})

在输入结束后，可以对其进行预处理。

但是在查询的时候st表不支持修改，只能按原始输入的数组进行查询操作

对于每一个查询 [l,r] , 回答是： max([l,l + 2 ^ s -1],[r - 2 ^ s + 1 , r]) ,其中 s 为 log_2^{(r-l+1)} 。

这样就能从区间的左端点和右端点分别进行 2 的整数次方个位置。取 max 即是整个区间的 max 。

对于每一次查询是 O(1) 的。

对于预处理是 O(n log n) 的。

其实这篇文章应该放到P3865的题解的。可惜不能再提交题解了。

模板：(AC)

#include <iostream>
using namespace std;
#define ll long long
const int N =1e5+5;
int log(int x){
    for(int i = 32;i >= 0;i--){
        if((1<<i) & x) return i;
    }
}
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
//int max(int a,int b){
//  if(a > b){
//      return a;
//  }
//  return b;
//}
int f[N][30];
int n,m; 
int l,r,t;
int i,j;
int main(){
    n=read();
    m = read();
    for(i = 1;i <= n;++i){
        f[i][0] = read();
    }
    for(j = 1;(1<<j) <= n;++j){
        for(i = 1;i + (1 << j)-1 <= n;++i){
            f[i][j] = max(f[i][j-1],f[i+(1 << (j - 1))][j - 1]);
        }
    }
    for(i = 1;i <= m;++i){
        l=read();
        r=read();
        t=log(r-l+1);
        printf("%d\n",max(f[l][t],f[r - (1 << t) + 1][t]));
    }
    return 0;
}