# 定义

$ST$ 表，是用于解决可重复贡献问题的数据结构

什么是可重复贡献问题？
可重复贡献问题是指对于运算 $opt$ ，满足 $x~opt~x=x$
例如：
max(x, x) = x ， gcd(x, x) = x ，所以 $RMD$ 和区间 $GCD$ 问题都是 == 可重复贡献问题，而区间和不满足这个性质。

什么是 RMQ？
区间最大（最小）值问题，传送门

# 模板题

# 题意

给定一个长度为 $N$ 的数列，和 $M$ 次询问，每一次询问包含一个区间 $l, r$ ，求出每一次询问的区间内数字的最大值
$1 \le N \le 10^5, 1 \le M \le 2 \cdot 10^6, a_i \in [0, 10^9], 1 \le l \le r \le N$

# 思路

# 暴力做法

对于每次询问都扫一遍 $l \to r$ 的所有数，每次查询复杂度 $O(N)$ 显然会爆

# ST 表正解

$ST$ 表基于倍增思想，可以做到 $O(n\log{n})$ 的预处理， $O(1)$ 时间的查询，但不能修改
基于倍增思想，我们考虑如何求出区间最大值。可以发现，如果按照一般的倍增流程，每次跳 $2^i$ 步的话，询问时的复杂度仍旧是 $O(\log n)$ ，并没有比线段树更优，反而预处理一步还比线段树慢
因为 max(x, x) = x ，可以发现，区间最大值是一个可重复贡献问题。所以，即使用来求解的预处理区间有重叠部分，只要这些区间的并是所求的区间，那么最终计算出的答案就是正确的
可以发现，只需使用至多两个预处理过的区间，便可以覆盖询问区间，也就是说询问时的时间复杂度可以被降至 $O(1)$ ，在处理有大量询问的题目时十分有效

# 具体实现如下

# 预处理

令 $f_{(i, j)}$ 表示区间 $[i, i + 2^j - 1]$ 的最大值（显然 $f_{(i,0)} = a_i$ ）
根据定义，第二维相当于倍增的时候跳了 $2^j - 1$ 步，则状态转移方程： $f_{(i,j)}=max(f_{(i, j-1)},f_{(i+2^{j-1},j - 1)})$

# 查询

对于每个询问 $[l,r]$ ，可以把他分为两部分： $[l,l+2^s-1]$ 和 $[r-2^s+1,r]$ ，其中 $s=\lfloor{\log_2 {(r-l+1)}}\rfloor$
因为这两个区间覆盖了 $[l,r]$ ，所以可以保证答案的正确性（如图示）
ST表-OIWiki

# 代码模板

$pre[i]$ 表示 $\lfloor{\log_2 i}\rfloor$

C++

#include <bits/stdc++.h>
#define int long long
#define endl '\n'

using namespace std;

constexpr int N = 2000001;

constexpr int logN = 21;
int f[N][logN + 1], preN[N + 1];

void pre() { // 准备工作，初始化
    preN[1] = 0, preN[2] = 1;
    for (int i = 3; i < N; i++)
        preN[i] = preN[i / 2] + 1;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> f[i][0];

    pre();

    for (int j = 1; j <= logN; 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]); // ST表具体实现
    
    for (int i = 1, x, y; i <= m; i++) {
        cin >> x >> y;
        int s = preN[y - x + 1];
        cout << max(f[x][s], f[y - (1 << s) + 1][s]) << endl;
    }

    return 0;
}

# ST 表特性

除 $RMQ$ 问题外，区间按位与，区间按位或，区间 $GCD$ 都是可重复贡献问题
$ST$ 表能较好的维护可重复贡献的区间信息（同时也应满足结合律），时间复杂度较低，代码量相对其他算法很小。但是， $ST$ 表能维护的信息非常有限，不能较好地扩展，并且不支持修改操作