ST表简介#

ST 表（Sparse Table，稀疏表）是一种用于在静态数组上进行快速查询的数据结构，特别适用于 idempotent operations（幂等操作），如最小值、最大值、最大公约数等。ST 表的构建时间复杂度为 $O(n \log n)$ ，查询时间复杂度为 $O(1)$ ，空间复杂度为 $O(n \log n)$ 。

ST表的使用场景#

ST表往往用于可以动态规划且需要频繁区间查询的场景。

区间查询#

ST表最常见的使用场景是区间查询，特别是当需要频繁查询某个区间的最小值、最大值或其他幂等操作时。由于ST表可以在 $O(1)$ 时间内返回查询结果，因此非常适合处理大量查询的情况。

状态转移#

在某些动态规划问题中，可能不能实现幂等操作，这时，ST表可以通过倍增来优化状态转移过程，达到快速查询的效果。例如P7167中需要频繁查看圆盘的容量并累加，这时可以使用ST表来快速查询从某个圆盘开始一定范围内的总容量。其实此时已经跟ST表关系不大了，主要是用ST表实现倍增。

ST表的构建和查询#

构建#

构建ST表的过程主要包括以下步骤：

初始化：创建一个二维数组 st，其中 st[i][j] 表示以 i 为起点，长度为 $2^j$ 的区间的查询结果。
填充：使用动态规划的方式填充 st 数组，利用之前计算的结果来构建更长的区间。状态转移方程通常为：

st[i][j] = operation(st[i][j - 1], st[i + 2^(j - 1)][j - 1])

其中 operation 是你需要进行的幂等操作，如最小值或最大值。

查询#

查询过程非常简单，给定一个区间 [L, R]，首先计算区间长度 k = floor(log2(R - L + 1))，然后使用预先计算好的 st 数组来返回查询结果，通常是通过合并两个重叠区间的结果或倍增合并不重叠区间来得到最终答案。例如：

若满足幂等操作，可以直接返回 operation(st[L][k], st[R - 2^k + 1][k])

若不满足幂等操作，可以通过倍增的方式合并多个区间的结果来得到最终答案。

1
result = initial_value;
2
for(int k = floor(log2(R - L + 1)); k >= 0; k--){
3
    if ((R - L + 1) >= 2^k){
4
     result = operation(result, st[L][k]);
5
     L += 2^k;
6
     // 这里不一定要有R，因为不满足幂等操作，所以R只是用来代表终止条件
7
     // L的位置转移不一定是连续的，所以需要根据实际情况来调整L的位置
8
    }
9
 }

案例#

gcd查询#

假设我们需要在一个数组中频繁查询某个区间的最大公约数（gcd）。我们可以使用ST表来预处理数组，使得每次查询都能在 $O(1)$ 时间内返回结果。

构建ST表：对于每个元素，初始化 st[i][0] 为该元素的值。然后使用动态规划填充 st 数组，根据状态转移方程计算更长区间的gcd。
查询：对于每个查询区间 [L, R]，计算 k = floor(log2(R - L + 1))，然后返回 gcd(st[L][k], st[R - 2^k + 1][k])。

下面是一个简单的示例代码片段，展示了如何构建和查询ST表以进行gcd查询：

1
#include <iostream>
2
#include <vector>
3
#include <cmath> // 包含 std::log2
4
#include <numeric> // 包含 std::gcd (C++17)
5
using namespace std;
6
const int MAXN = 100005; // 稍微开大一点防止越界
7
int st[MAXN][20]; // 假设最大数组长度为100000，20是因为20 > log2(100000)
8
// st[L][k] 表示从 L 开始，长度为 2^k 的区间的 gcd 结果，即覆盖 [L, L + 2^k - 1]
9

10
void buildST(const vector<int>& arr, int n) {
11
    for (int i = 0; i < n; i++) {
12
        st[i][0] = arr[i];
13
    }
14
    for (int j = 1; (1 << j) <= n; j++) {
15
        for (int i = 0; i + (1 << j) - 1 < n; i++) {
16
            st[i][j] = std::gcd(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
17
        }
18
    }
19
}
20

21
int query(int L, int R) {
22
    int k = std::log2(R - L + 1);
23

24
    // st[R - (1 << k) + 1][k] 表示以 R 结尾，长度为 2^k 的区间的 gcd 结果，即覆盖 [R - 2^k + 1, R]
25
    // 因为 gcd 是幂等操作（重叠区间不影响结果），合并两部分即可覆盖整个区间 [L, R]
26
    return std::gcd(st[L][k], st[R - (1 << k) + 1][k]);
27
}
28

29
int main() {
30
    int n, q;
31
    cin >> n >> q;
32
    vector<int> arr(n);
33
    for (int i = 0; i < n; i++) {
34
        cin >> arr[i];
35
    }
36
    buildST(arr, n);
37
    while (q--) {
38
        int L, R;
39
        cin >> L >> R;
40
        cout << query(L, R) << "\n";
41
    }
42
    return 0;
43
}

P7167#

在洛谷P7167中，我们需要处理大量的查询，查询内容涉及到圆盘的容量和累加。通过使用ST表，我们可以快速查询从某个圆盘开始一定范围内的总容量，从而显著提高查询效率。具体实现时，可以将圆盘的容量预处理到ST表中，然后根据查询需求进行快速查询和累加。

下面是一个示例代码片段，展示了如何使用ST表来处理P7167中的查询：

1
#include <iostream>
2
using namespace std;
3

4
const int MAXN = 100005;
5
int D[MAXN], C[MAXN];   // D[i]：第 i 个圆盘的直径，C[i]：第 i 个圆盘的容量
6
int nxt[MAXN][20];      // nxt[i][j] (next)：表示从圆盘 i 溢出后，向下跳跃 2^j 次最终到达的圆盘编号
7
int sum[MAXN][20];      // sum[i][j]：从圆盘 i 溢出后，向下跳跃 2^j 次路径上所有圆盘的容量累加和
8
int stk[MAXN], top = 0; // 单调栈及栈顶索引，用于寻找下方第一个直径更大的圆盘。
9

10
int main() {
11

12
    int n, q;
13
    cin >> n >> q;
14

15
    for (int i = 1; i <= n; i++) {
16
        cin >> D[i] >> C[i];
17
    }
18

19
    // 单调栈，寻找每个圆盘水流溢出后的下一个目标圆盘，作为倍增表的第一列，并记录第一列的容量累加和
20
    for (int i = 1; i <= n; i++) {
21
        while (top > 0 && D[stk[top]] < D[i]) {
22
            nxt[stk[top]][0] = i;
23
            sum[stk[top]][0] = C[stk[top]];
24
            top--;
25
        }
26
        stk[++top] = i;
27
    }
28

29
    // 剩下的圆盘没有下方满足条件的圆盘，最终流向水池(虚设为0)
30
    while (top > 0) {
31
        nxt[stk[top]][0] = 0;
32
        sum[stk[top]][0] = C[stk[top]];
33
        top--;
34
    }
35

36
    // 构建倍增表 (ST表的变种体现)
37
    for (int j = 1; j <= 18; j++) {
38
        for (int i = 1; i <= n; i++) {
39
            nxt[i][j] = nxt[nxt[i][j - 1]][j - 1];
40
            sum[i][j] = sum[i][j - 1] + sum[nxt[i][j - 1]][j - 1];
41
        }
42
    }
43

44
    // 处理查询
45
    while (q--) {
46
        int R, V;
47
        cin >> R >> V;
48
        int curr = R;
49

50
        // 倍增跳跃寻找水流的终点
51
        for (int j = 18; j >= 0; j--) {
52
            if (nxt[curr][j] != 0 && sum[curr][j] < V) {
53
                V -= sum[curr][j];
54
                curr = nxt[curr][j];
55
            }
56
        }
57

58
        // 经过最大的跳跃后，如果剩余水容量仍超出当前盘的容量，说明会最终流入水池
59
        if (V <= C[curr]) cout << curr << '\n';
60
        else cout << 0 << '\n';
61
    }
62

63
    return 0;
64
}