【数据结构】ST表

ST表

ST表基于倍增的思想，可以做到的离线预处理和​的在线查询。它可以用于解决满足结合律的可重复贡献问题。

可重复贡献问题 是指对于运算​​​ ，满足​​​ ，则对应的区间询问就是一个可重复贡献问题。例如，最大值有​​ ，gcd 有​​ ，所以 RMQ 和区间 GCD 就是一个可重复贡献问题。像区间和就不具有这个性质，如果求区间和的时候采用的预处理区间重叠了，则会导致重叠部分被计算两次，这是我们所不愿意看到的。另外， opt还必须满足结合律才能使用 ST 表求解。

具体实现如下：

令表示区间​的最大值（或其他意义）。

显然。

我们将​表示的区间划分为两部分，分别是​和​，在离散意义下，两个区间刚好可以覆盖原有区间，因此有状态转移方程：

。

接下来对于查询区间中的最大值，我们将查询区间分为和​，令，得，此时可证明两区间可以覆盖原区间（不保证交集为空）。

即

模板

#include <bits/stdc++.h>
using namespace std;
inline int read(){
    int x = 0,f = 1;
    char c = getchar();
    while (!isdigit(c)){
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (isdigit(c)){
        x = x * 10 + c - '0';
        c = getchar(); 
    }
    return x * f;
}
const int N = 1e5 + 5;
int f[N][20];
int n,m;
int main(){
    ios::sync_with_stdio(false),cin.tie(0);
    n = read(),m = read();
    for (int i = 1;i <= n;++i){
        f[i][0] = read();
    }

    for (int i = 1;i <= __lg(N);++i){
        for (int j = 1;j + (1 << i) - 1 <= n;++j){
            f[j][i] = max(f[j][i-1],f[j+(1<<(i-1))][i-1]);
        }
    }
    //puts("YES");
    while (m--){
        int l,r;
        l = read(),r = read();
        int s = __lg(r-l+1);
        printf("%d\n",max(f[l][s],f[r-(1<<s)+1][s]));
    }
    return 0;
}

统计区间gcd

const int N = 1e4 + 5;
int f[N][20];
int n,m;
int main(){
    ios::sync_with_stdio(false),cin.tie(0);
    cin >> n >> m;
    for (int i = 1;i <= n;++i){
        cin >> f[i][0];
    }

    for (int i = 1;i <= __lg(N);++i){
        for (int j = 1;j + (1 << i) - 1 <= n;++j){
            f[j][i] = __gcd(f[j][i-1],f[j+(1<<(i-1))][i-1]);
        }
    }

    while (m--){
        int l,r;
        cin >> l >> r;
        int s = __lg(r-l+1);
        printf("%d\n",__gcd(f[l][s],f[r-(1<<s)+1][s]));
    }
    return 0;
}