st 表

st 表是一种维护可重复贡献运算，\(O(n\log n)\) 预处理，\(O(1)\) 查询的数据结构。

可重复贡献的运算

若一个运算满足结合律 \(a\otimes (b\otimes c)=(a\otimes b)\otimes c\)，且满足 \(a\otimes a=a\)，则这种运算可以使用 st 表维护。我们常见的此种运算有最大公约数 \(gcd\)、最大值和最小值 \(\min,\max\)，都可以使用 st 表维护，进行快速查询。

一维 st 表模板

#include<iostream>
using namespace std;
const int N = 1E5 + 10;
const int LOGN = 20;

int n, q;
int st[N][LOGN], lg[N];

int main() {

    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> q;
    for(int i = 1; i <= n; i++) {
        cin >> st[i][0];
    }

    for(int j = 1; j < LOGN; 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]);
        }
    }

    for(int i = 1; i < N; i++) {
        lg[i] = lg[i - 1] + (i == (1 << lg[i - 1] + 1));
    }

    while(q--) {
        int l, r;
        cin >> l >> r;
        cout << max(st[l][lg[r - l + 1]], st[r - (1 << lg[r - l + 1]) + 1][lg[r - l + 1]]) << '\n';
    }

    return 0;
}