ST表

ST 表（Sparse Table，稀疏表）是用于解决 可重复贡献问题 的数据结构。

可重复贡献问题 是指对于运算 ，满足 ，则对应的区间询问就是一个可重复贡献问题。例如，最大值有 ， 有 ，所以 RMQ 和区间 GCD 就是一个可重复贡献问题。

c++模板

const int N = 2e5 + 5;
int dp[N][100];

void init(vector<int> &a) // 初始化
{
    int n = a.size() - 1; // 下标从1开始
    int len = log2(n);
    for(int i = 1; i <= n; i++) {
        dp[i][0] = a[i];
    }
    for(int j = 1; j <= len; j++) {
        for(int i = 1; i <= n - (1 << j) + 1; i++) {
            dp[i][j] = max(dp[i][j - 1], dp[i + (1 << (j - 1))][j - 1]);
        }
    }
}

int query(int l, int r) // 查询l到r的最大值
{
    int o = log2(r - l + 1);
    return max(dp[l][o], dp[r - (1 << o) + 1][o]);
}