ST

知识传送门

作用: (O(nlogn))预处理，(O(1)) 回答 区间最大值最小值信息，不支持修改

1. (f[i][j]) 储存了区间([i,i+2^j-1])的最大值 or 最小值
2. 转移方程: (f[i][j] = f[i][j-1] + f[i+(1<<(j-1))][j-1])
   
3. 查询区间([l,r]),总能找到一个(k(2^kle r-l+1,2^{k+1}>r-l+1))。答案就是(max(f[l][k],f[r-(1<<k)+1][k])
4. 可以使用(k = {frac {log(n)}{log(2)}})来找k，也可以进行预处理
   • (logn[1] = 0)
   • (logn[n] = logn[n/2]+1)

ST模板题

#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int n,m;
int a[N];
int f[N][20];
int logn[N];
void init(){
    logn[1] = 0;
    logn[2] = 1;
    for(int i=3;i<N;i++){
        logn[i] = logn[i/2] + 1;
    }
}
int main(){
    init();
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)f[i][0] = a[i];
    int t = logn[n] + 1;
    for(int j=1;j<=t;j++){
        for(int i=1;i<=n-(1<<j)+1;i++)
            f[i][j] = max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
    }
    int l,r;
    while(m--){
        scanf("%d%d",&l,&r);
        int k = logn[r-l+1];
        //cout << r - l + 1 << ' ' << k << endl;
        int res = max(f[l][k],f[r-(1<<(k))+1][k]);
        printf("%d
",res);
    }
    return 0;
}