ACM模板库

ACM模板库


维护区间最大值ST表

const int maxn = 3e5+5;
int st[maxn][25];
int n
ll a[maxn];
int lg[300005] = {-1};
void getlog(){
    for(int i = 1; i <= 300005; i++) lg[i] = lg[i/2] + 1;
    return;
}
void init(){
    for(int i = 1; i <= n; i++){
        st[i][0] = a[i];        //st表存数组值
    } 
    for(int j = 1; (1 << j) <= n; j++){
        for(int i = 1; i + (1 << (j-1)) <= n; i++){
            st[i][j] = max(st[i][j-1], st[i+(1<<(j-1))][j-1]);        //此条语句
        }
    }
}
int query(int l, int r){
    int k = lg[r-l+1];
    return max(st[l][k], st[r-(1<<k)+1][k]);  //此条语句
}

页面列表

ITEM_HTML