ST表_v2

ST 表模板整理。

ST 表

用于解决 可重复贡献问题 的数据结构。

以下为维护区间max模板，维护其他信息时相应修改即可。

struct ST{
    vector<vector<int>>st;
    vector<int>log;

    ST(vector<int>v){
        int n = v.size();
        int max_log = log2(n) + 1;

        log.resize(n + 1);
        for(int i = 2; i <= n; i++){
            log[i] = log[i >> 1] + 1;
        }

        st.resize(n, vector<int>(max_log));
        for(int i = 0; i < n; i++){
            st[i][0] = v[i];
        }
        for(int j = 1; (1 << j) <= n; j++){
            for(int i = 0; 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 = log[r - l + 1];
        return max(st[l][k], st[r - (1 << k) + 1][k]);
    }
};