ST表

ST 表能解决所有符合结合律且可以重复贡献的信息查询：最大/小值，最大公约数，最小公倍数，按位或/与

但是如果要区间修改，需要用到线段树

struct ST {
    const int n, k;
    vector<int> in1, in2;
    vector<vector<int>> Max, Min;
    ST(int n) : n(n), in1(n + 1), in2(n + 1), k(__lg(n)) {
        Max.resize(k + 1, vector<int>(n + 1));
        Min.resize(k + 1, vector<int>(n + 1));
    }
    void init() {
        for (int i = 1; i <= n; i++) {
            Max[0][i] = in1[i];
            Min[0][i] = in2[i];
        }
        for (int i = 0, t = 1; i < k; i++, t <<= 1) {
            const int T = n - (t << 1) + 1;
            for (int j = 1; j <= T; j++) {
                Max[i + 1][j] = max(Max[i][j], Max[i][j + t]);
                Min[i + 1][j] = min(Min[i][j], Min[i][j + t]);
            }
        }
    }
    int getMax(int l, int r) {
        if (l > r) {
            swap(l, r);
        }
        int k = __lg(r - l + 1);
        return max(Max[k][l], Max[k][r - (1 << k) + 1]);
    }
    int getMin(int l, int r) {
        if (l > r) {
            swap(l, r);
        }
        int k = __lg(r - l + 1);
        return min(Min[k][l], Min[k][r - (1 << k) + 1]);
    }
};

P3865 【模板】ST 表 - 洛谷

线段树也可以过(好像需要快读，将我模板中的 ll 改为 int 才能过)，但是常数较大

void solve() {
    int n, m;
    n = read(), m = read();
    for (int i = 1;i <= n;i++) {
        a[i] = read();
    }
    build(1, 1, n);
    while (m--) {
        int l, r;
        l = read(), r = read();
        cout << query(1, l, r) << '\n';
    }
}

int f[N][22];
void solve() {
    int n, m;cin >> n >> m;
    for (int i = 1;i <= n;i++)cin >> f[i][0];
    for (int j = 1;j <= 20;j++) {
        for (int i = 1;i + (1 << j) - 1 <= n;i++) {
            f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
        }
    }
    for (int i = 1;i <= m;i++) {
        int l, r;cin >> l >> r;
        int k = log2(r - l + 1);// int k = __lg(r - l + 1);
        cout << max(f[l][k], f[r - (1 << k) + 1][k]) << '\n';
    }
}

P2880 Balanced Lineup G 求最大值和最小值之差

int f1[50010][22], f2[50010][22];
void solve() {
    int n, m;cin >> n >> m;
    for (int i = 1;i <= n;i++)cin >> f1[i][0], f2[i][0] = f1[i][0];
    for (int j = 1;j <= 20;j++) {
        for (int i = 1;i + (1 << j) - 1 <= n;i++) {
            f1[i][j] = max(f1[i][j - 1], f1[i + (1 << (j - 1))][j - 1]);
            f2[i][j] = min(f2[i][j - 1], f2[i + (1 << (j - 1))][j - 1]);
        }
    }
    for (int i = 1;i <= m;i++) {
        int l, r;cin >> l >> r;
        int k = log2(r - l + 1);// int k = __lg(r - l + 1);
        cout << max(f1[l][k], f1[r - (1 << k) + 1][k]) - min(f2[l][k], f2[r - (1 << k) + 1][k]) << '\n';
    }
}

练习：

P1198 最大数

现在请求你维护一个数列，要求提供以下两种操作：

查询操作。

语法：Q L

功能：查询当前数列中末尾 $L$ 个数中的最大的数，并输出这个数的值。

限制： $L$ 不超过当前数列的长度。 $(L > 0)$

插入操作。

语法：A n

功能：将 $n$ 加上 $t$ ，其中 $t$ 是最近一次查询操作的答案（如果还未执行过查询操作，则 $t = 0$ ），并将所得结果对一个固定的常数 $D$ 取模，将所得答案插入到数列的末尾。

限制： $n$ 是整数（可能为负数）并且在长整范围内。

注意：初始时数列是空的，没有一个数。

Solution

线段树/ST 表

在末尾插入对 ST 表的结构不会造成破坏，可以使用

线段树

#define int long long
#define lc u<<1
#define rc u<<1|1
int a[200010];int m, mod;
struct Tree { //线段树
    ll l, r, max;
}tr[800010];
void pushup(ll u) { //上传
    tr[u].max = max(tr[lc].max, tr[rc].max);
}
void build(ll u, ll l, ll r) { //建树
    tr[u] = {l,r,a[l]};
    if (l == r) return;
    ll m = l + r >> 1;
    build(lc, l, m);
    build(rc, m + 1, r);
    pushup(u);
}
ll query(ll u, ll l, ll r) { 
    if (l <= tr[u].l && tr[u].r <= r) return tr[u].max;
    ll m = tr[u].l + tr[u].r >> 1;
    ll ans = -1;
    if (l <= m) ans = max(ans, query(lc, l, r));
    if (r > m) ans = max(ans, query(rc, l, r));
    return ans;
}
void change(ll u, ll x, ll v) { 
    if (x == tr[u].l && tr[u].r == x) {
        tr[u].max = v;  return;
    }
    ll m = tr[u].l + tr[u].r >> 1;
    if (x <= m) change(lc, x, v);
    else change(rc, x, v);
    pushup(u);
}
void solve() {
    int n = 0, t = 0;
    cin >> m >> mod;
    build(1, 1, m);
    while (m--) {
        char op;cin >> op;
        if (op == 'A') {
            int x;cin >> x;
            ++n;
            change(1, n, (x + t) % mod);
        } else {
            int l;cin >> l;
            t = query(1, n - l + 1, n);
            cout << t << '\n';
        }
    }
}

P3865 【模板】ST 表 - 洛谷

P2880 Balanced Lineup G 求最大值和最小值之差

练习 ：

P1198 最大数

Solution

练习：