ST表

我们时常会遇到对一个固定序列进行反复区间查询的问题。例如，查询一个给定区间内的最大值、最小值，或是最大公约数等。这类问题统称为静态区间查询问题，因为数据序列本身不会发生改变。对于这类问题，如果每次查询都暴力扫描一遍区间，当查询次数较多时，时间复杂度往往难以承受。ST表（Sparse Table，稀疏表）算法应运而生，它是一种基于倍增思想的预处理技术，能够在的预处理后，以的惊人效率回答特定类型的区间查询，是解决此类问题的有力武器。

1. RMQ问题与朴素解法

让我们从一个经典问题入手：区间最值查询（Range Minimum/Maximum Query, RMQ）。

1.1 RMQ问题定义

给定一个长度为的静态数组。RMQ问题要求对于给定的若干查询（），找出数组在该闭区间内的最小值或最大值。为明确起见，我们后续主要以区间最小值为例进行讨论，区间最大值同理。

形式化地，对于查询，我们需要计算。

1.2 暴力解法

最直观的想法是，对于每个查询，直接遍历数组从下标到的所有元素，找到其中的最小值。

// 题意概括: 给定数组a，多次查询区间[l,r]中的最小值。
// 暴力解法示例
#include <bits/stdc++.h>
using namespace std;
using ll = long long; // 虽然本例是int，但保持习惯

// a: 输入数组
// l, r: 查询区间的左右端点 (0-indexed)
int qry(const vector<int>& a, int l, int r) {
    if (l > r) return INT_MAX; // 或其他错误处理
    int mval = a[l];
    for (int i = l + 1; i <= r; ++i) {
        mval = min(mval, a[i]);
    }
    return mval;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n, q_cnt; // n: 数组大小, q_cnt: 查询次数
    cin >> n >> q_cnt;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    for (int k = 0; k < q_cnt; ++k) {
        int l, r;
        cin >> l >> r; // 假设输入已经是0-indexed
        cout << qry(a, l, r) << "\n";
    }

    return 0;
}

复杂度分析:

预处理时间复杂度: （如果数组已读入，则不算读入时间）。
单次查询时间复杂度: （最坏情况下接近）。
总时间复杂度 (对于次查询): 。

当和的规模达到级别时，的复杂度将高达，这在通常几秒的时限内是无法接受的。我们需要更高效的算法。

2. ST表的核心思想：倍增

ST表的核心威力来源于倍增（Binary Lifting / Doubling）思想。倍增是一种将问题规模按2的幂次进行划分和组合的技巧。在ST表中，我们预先计算出所有形如的区间的最值。任何一个区间都可以被巧妙地表示为两个（可能重叠的）长度为的预计算区间的组合。

2.1 倍增法的概念

想象一下你要从点跳到点。你可以一步一步跳，也可以利用预先设置好的“跳板”，这些跳板允许你一次跳过个单位的距离。通过组合这些次幂的跳跃，你可以高效地到达任何距离的目标。这就是倍增的直观感受。在ST表中，“距离”被映射为“区间长度”。

2.2 ST表的构造：预处理

ST表用一个二维数组 st[i][k] 来存储预计算的结果。

状态定义:
表示原始数组中，以为起点，长度为的区间内的最值。即，区间的最值。

例如，对于最小值查询：

状态转移方程:
考虑如何计算。一个长度为的区间可以被看作是两个长度为的子区间的并集：

第一个子区间：从开始，长度为。即。其最值为。
第二个子区间：从开始，长度为。即，也就是。其最值为。

这两个子区间恰好无重叠地（或者说，首尾相接）覆盖了整个区间。因此，整个区间的最值就是这两个子区间最值的最值。

这个递推关系是ST表构造的核心。

初始化 (Base Case):
当时，区间的长度为。所以表示区间的最值，这显然就是元素本身。

预处理过程:
预处理通常采用两层循环：

外层循环遍历，从开始，直到超出数组长度。的最大值约为。
内层循环遍历，从开始。对于每个和，我们要计算。需要确保区间不越界，即，或者。

为了方便计算的最大值以及后续查询中快速得到，我们可以预处理一个 lg 数组，其中 lg[x] 存储。
lg[1] = 0
lg[x] = lg[x/2] + 1 for .

C++ 代码实现 (预处理):
假设我们求区间最小值。

// N_MAX: 数组最大长度
// K_MAX: log2(N_MAX) 的最大值，大约 20 for N_MAX = 10^6
const int N_MAX = 100005; // 示例最大长度
const int K_MAX = 17;     // floor(log2(100005)) approx 16.6, so 17 is safe for k up to 16.
                          // 若区间长度为2^k, k最大为16, 则需要st[][16]
                          // 若k从0开始, st第二维大小为K_MAX+1
                          // 严格来说， K_MAX 应该是 floor(log2(N_MAX))
                          // 例如 N=8, K_MAX = 3. st[i][3]代表长度8.
                          // N=7, K_MAX = 2. st[i][2]代表长度4.

int st[N_MAX][K_MAX + 1]; // st[i][k]
int lg[N_MAX + 1];      // lg[len] = floor(log2(len))

// a: 输入数组 (0-indexed)
// n: 数组大小
void bld(const vector<int>& a, int n) {
    // 1. 预处理log2数组
    lg[1] = 0;
    for (int i = 2; i <= n; ++i) {
        lg[i] = lg[i / 2] + 1;
    }

    // 2. 初始化 st[i][0]
    for (int i = 0; i < n; ++i) {
        st[i][0] = a[i];
    }

    // 3. 递推计算 st[i][k]
    // k 代表 2^k 这个长度级别
    // 1 << k 即为 2^k
    for (int k = 1; (1 << k) <= n; ++k) { // k 从1开始，因为k=0已经初始化
                                         // (1 << k) 是区间长度，不能超过n
        // i 是区间的起始点
        // 区间是 [i, i + (1 << k) - 1]
        // 要求 i + (1 << k) - 1 < n  => i + (1 << k) <= n
        for (int i = 0; i + (1 << k) <= n; ++i) {
            st[i][k] = min(st[i][k - 1], st[i + (1 << (k - 1))][k - 1]);
            // st[i][k-1] 对应区间 [i, i + 2^(k-1) - 1]
            // st[i + 2^(k-1)][k-1] 对应区间 [i + 2^(k-1), i + 2^(k-1) + 2^(k-1) - 1]
        }
    }
}

代码解释:

lg 数组的预处理：lg[i] 存储。这是为了后续查询时能获得区间长度对应的值。
st[i][0] 初始化：长度为的区间的最小值就是。
递推：
- 外层循环 k 从开始，因为的情况已经处理。(1 << k) 代表当前要处理的区间长度。这个长度不能超过总长。
- 内层循环 i 是区间的起始下标。要保证区间的末尾不超过，即。
- 转移方程 st[i][k] = min(st[i][k-1], st[i + (1 << (k-1))][k-1]); 准确实现了上述的递推关系。注意 (1 << (k-1)) 就是。

复杂度分析 (预处理):

lg 数组预处理时间：。
st 数组填充：
- 外层循环 k 大约执行次。
- 内层循环 i 最多执行次。
- 总时间复杂度为。
空间复杂度：lg 数组，st 数组。所以总空间复杂度为。

3. ST表的查询操作

预处理完成后，我们就可以高效地进行区间查询了。

3.1 查询原理

对于一个查询区间，其长度为。
我们的目标是利用预处理好的值来地得到结果。
ST表采用一种巧妙的覆盖方式：选取一个合适的值，使得，并且用两个长度为的区间来覆盖。
这个可以取为。可以通过预处理的 lg 数组得到：k_opt = lg[len]。

有了，我们考虑以下两个区间：

第一个区间：从开始，长度为。即。其最值为。
第二个区间：以为结束点，长度为。即。其最值为。

这两个区间长度都是。它们共同覆盖了整个区间。
为什么能覆盖？因为，所以。

第一个区间的右端点。
第二个区间的左端点。
由于 (当时等号成立，否则因为 ), 这两个区间必然会发生重叠（或者在时恰好首尾相接，但实际是不是的幂时，会大于等于）。
这意味着，中的每一个元素都至少被这两个区间中的一个所包含。

关键点：运算的幂等性 (Idempotence)
如果我们要查询的操作（比如 min 或 max）具有幂等性，即，那么即使两个子区间有重叠，重叠部分的元素被计算两次也不会影响最终结果。
例如，。元素在重叠区被考虑了两次，但不影响最小值。
常见的幂等运算有：

取最小值 (min)
取最大值 (max)
按位与 (AND)
按位或 (OR)
最大公约数 (GCD) (注意： if )

对于这类幂等运算，查询的结果就是上述两个预计算区间结果的运算值。

其中。

如果运算不具有幂等性（如求和、异或），这种的重叠查询方法就不适用了。对于求和这类运算，需要将区间分解成多个不重叠的长度的区间，查询复杂度会是。我们将在后续章节探讨这一点。目前，我们专注于幂等运算的查询。

3.2 计算

如前所述，。
利用预处理好的 lg 数组，k_opt = lg[r - l + 1]。这步是的。

3.3 查询公式 (以最小值为例)

对于查询区间：

计算区间长度。
查找。
结果为。

C++ 代码实现 (查询)

// 假设 bld 函数已调用，st 和 lg 数组已填充
// l, r: 查询区间的左右端点 (0-indexed)
int qry(int l, int r) {
    int len = r - l + 1;
    int k = lg[len]; // k = floor(log2(len))
    // 区间1: [l, l + 2^k - 1], 对应 st[l][k]
    // 区间2: [r - 2^k + 1, r], 对应 st[r - (1 << k) + 1][k]
    return min(st[l][k], st[r - (1 << k) + 1][k]);
}

复杂度分析 (查询):

计算 len：。
查找 k from lg array：。
访问 st 数组两次并取 min：。
总查询时间复杂度为。

这是ST表最吸引人的特性之一：经过的一次性投入后，每次查询都快如闪电。

4. ST表应用实例：区间最值查询 (RMQ)

现在我们将预处理和查询部分整合起来，给出一个完整的RMQ问题（查询区间最小值）的解决方案。

4.1 问题描述

给定一个长度为的整数序列和个查询。每个查询给出两个整数，要求输出序列在下标区间 (闭区间，0-indexed) 内的最小值。
。

4.2 完整代码实现

#include <bits/stdc++.h> // 万能头文件

using namespace std;
using ll = long long; // 定义ll为long long类型

const int N_MAX = 100005; // 数组最大长度
const int K_MAX = 17;     // log2(N_MAX) 大约是16.6，所以k最大取到16，数组第二维大小为17
                          // (1 << 16) = 65536, (1 << 17) = 131072

int st[N_MAX][K_MAX];   // st[i][k] 存储区间 [i, i + 2^k - 1] 的最小值
int lg[N_MAX + 1];      // lg[len] 存储 floor(log2(len))

// 预处理函数
// a: 输入数组 (0-indexed)
// n: 数组大小
void bld(const vector<int>& a, int n) {
    lg[1] = 0;
    for (int i = 2; i <= n; ++i) {
        lg[i] = lg[i / 2] + 1;
    }

    for (int i = 0; i < n; ++i) {
        st[i][0] = a[i];
    }

    // k 表示 2^k 这个长度级别
    for (int k = 1; k < K_MAX; ++k) { // k 从1开始，因为k=0已初始化
                                      // 确保 2^k <= n，或者说 k <= lg[n]
        if (!((1 << k) <= n)) break; // 如果当前2^k长度已超过n，后续更长的也超，可提前退出
        // i 是区间的起始点
        // 区间是 [i, i + (1 << k) - 1]
        // 要求 i + (1 << k) - 1 < n  => i + (1 << k) <= n
        for (int i = 0; i + (1 << k) <= n; ++i) {
            st[i][k] = min(st[i][k - 1], st[i + (1 << (k - 1))][k - 1]);
        }
    }
}

// 查询函数
// l, r: 查询区间的左右端点 (0-indexed)
int qry(int l, int r) {
    if (l > r) return INT_MAX; // 处理无效区间，根据题目要求可能不同
    int len = r - l + 1;
    int k = lg[len]; 
    return min(st[l][k], st[r - (1 << k) + 1][k]);
}

int main() {
    ios::sync_with_stdio(0); // 关闭与C标准IO的同步
    cin.tie(0); cout.tie(0); // 解除cin/cout的绑定

    int n, m; // n: 数组元素个数, m: 查询次数
    cin >> n >> m;

    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    bld(a, n); // 构建ST表

    for (int i = 0; i < m; ++i) {
        int l, r;
        cin >> l >> r; // 假设题目输入是0-indexed
        // 如果题目是1-indexed, 需要转换: cin >> l >> r; l--; r--;
        cout << qry(l, r) << "\n";
    }

    return 0;
}

4.3 代码剖析与细节

K_MAX 的选择：K_MAX 应该是（如果从用到）。对于 , . 所以的最大值是。st 数组的第二维大小声明为 K_MAX = 17 (或 16+1) 足够了。在 bld 函数中，k 的循环条件 k < K_MAX 和 (1 << k) <= n 共同控制了 k 的范围，确保不会越界访问 st 也不会进行不必要的计算。
lg 数组的预计算：这个数组至关重要，它使得查询时计算的操作是的。如果没有它，每次查询计算对数将是或者需要使用 __builtin_clz (GCC/Clang) 等内建函数。
0-based vs 1-based indexing: 代码示例统一使用0-based indexing，这与C++ vector 的习惯一致。竞赛题目有时会使用1-based indexing，此时需要在读入查询的后进行调整（例如 l--, r--）。
边界条件 bld 函数中 k 的循环: for (int k = 1; (1 << k) <= n; ++k) 是一种常见的写法。另一种是 for (int k = 1; k <= lg[n]; ++k)。后者依赖 lg[n] 被正确计算。如果 k 从 0 开始到 lg[n]，那么 K_MAX 应为 lg[N_MAX]+1。我的代码里 k 从 1 开始，到 K_MAX-1 (即 16)，st 第二维大小是 K_MAX。st[i][k] 的 k 代表的长度，所以 k 的范围是。
- 修正 bld 中 k 的循环：for (int k = 1; k < K_MAX; ++k) 配合 if (!((1 << k) <= n)) break; 是安全的。或者更精确地 for (int k = 1; k <= lg[n]; ++k)，前提是 lg[n] 已正确计算，并且 K_MAX 足够大以容纳 lg[n]。对于 st[N_MAX][K_MAX] 的声明，K_MAX 通常指最大可能的值再加1 (如果是数组下标)，或就是最大值 (如果 K_MAX 代表的是这个级别)。这里 K_MAX=17 意味着可以取到。
查询中 r - (1 << k) + 1: 这是计算第二个区间的起始位置。1 << k 是。这个起始点加上长度再减1就是。所以。

5. ST表性质探讨

理解ST表的性质有助于我们判断其适用场景，并与其他数据结构进行比较。

5.1 适用运算

ST表的构造过程（递推式）要求运算 op 满足**结合律 (Associativity)**。
即。
常见的满足结合律的运算有：加法、乘法、最大值、最小值、按位与、按位或、异或、最大公约数、矩阵乘法等。

对于ST表能够实现查询（即使用两个可能重叠的区间和合并结果），运算 op 除了满足结合律外，还必须具有**幂等性 (Idempotence)**。
即。
如前所述，min, max, gcd, lcm (需注意处理0的情况), 按位AND, 按位OR 都是幂等运算。

如果运算不具有幂等性呢？
例如，区间和、区间异或和。
对于这类运算，我们不能使用上述的重叠查询法，因为重叠部分元素会被计算两次，导致结果错误（如区间和会偏大）。
但是，ST表本身（即的预处理）仍然可以进行，因为构造过程依赖的是结合律，它将一个大区间分解为两个不重叠（或恰好相邻）的小区间。
对于非幂等但满足结合律的运算，查询区间时，需要将该区间精确地拆分为个不重叠的、预计算好的区间块。
例如，要查询区间的和：

// 伪代码: 查询区间[L,R]的和 (O(log N) 查询)
// S ans = IDENTITY_ELEMENT; // 和的单位元是0
// for k from floor(log2(N)) down to 0:
//   if L + (1 << k) - 1 <= R: // 如果长度为2^k的块 [L, L + 2^k - 1] 在 [L,R] 内
//     ans = ans op st[L][k];
//     L = L + (1 << k);      // L指针向右移动2^k
// return ans;

这种查询方式的时间复杂度是，因为一个任意区间最多能被分解成个（实际上是个，每种长度的块最多用两个，一个在左端一个在右端，但标准分解是贪心取最大块）预计算的区间。

因此，ST表对于幂等运算是预处理、查询；对于仅满足结合律的非幂等运算，是预处理、查询。

5.2 静态数据结构

ST表是一个典型的静态数据结构。这意味着一旦预处理完成，原始数组的内容就不能再修改了。如果数组中的任何一个元素发生改变，整个ST表（或者至少是依赖该元素的相关部分）都需要重新计算，最坏情况下需要的时间重建。
这与线段树、树状数组等动态数据结构形成对比，后者通常支持或类似复杂度的单点修改和区间查询。
因此，ST表最适用于数据固定不变，但查询非常频繁的场景。

5.3 空间复杂度权衡

ST表的空间复杂度为。当非常大时（例如 , ），这可能会消耗数十MB的内存，需要根据题目内存限制进行评估。
例如，, 。st[10^6][20] 的 int 类型数组大约需要。
作为对比：

暴力法：空间（存储原始数组）。
线段树（用于RMQ）：空间（标准实现是或的节点数）。
分块（用于RMQ）：预处理块信息或，数组本身。

如果空间非常紧张，而又很大，ST表可能不是最佳选择。但其查询的极致速度是其巨大优势。

6. ST表与非幂等运算

我们在前面提到，ST表能够实现区间查询的关键在于利用两个可能重叠的子区间合并结果，这要求运算具有幂等性。如果运算不具有幂等性，例如区间和、区间异或和，那么重叠部分的元素会被重复计算，导致结果错误。

例如，求区间的和。若且，则并不等于，因为重叠区间的元素被加了两次。

6.1 查询策略

尽管查询不再适用，ST表的预处理结构（表示区间的运算结果）本身仍然是有效的，只要运算满足结合律。我们可以将任意查询区间分解为个互不重叠的、预处理好的区间块，然后将这些块的结果合并起来。

分解方法是贪心的：从开始，尝试覆盖尽可能长的次幂长度的区间，该区间需完全包含在内。
具体来说，对于查询区间，其长度为。我们可以从大到小遍历（从或开始，到）。如果当前长度的区间能够完全包含在剩余待查询区间内（即），我们就将的结果计入总答案，并将更新为。重复此过程直到。

示例：区间求和
假设原始数组 ()。

(长度2):
(长度4):
(长度8):

查询区间 (元素 )，长度为。
。

: . . 区间 (元素 )。 (查询右端点)。
采纳 (值为 )。
. 更新。剩余查询区间。
: . . 区间 (元素 )。。
采纳 (值为 )。
. 更新。剩余查询区间 ()，结束。
正确和为。

6.2 代码实现 (区间和)

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int N_MAX = 100005;
const int K_MAX = 17; // floor(log2(N_MAX)) approx 16.6

ll st[N_MAX][K_MAX]; // 存储区间和
// lg 数组在这里不是必须的，因为 k 是从大到小遍历
// 但如果需要精确的 log2(len) 开始遍历，则仍有用

// a: 输入数组 (0-indexed)
// n: 数组大小
void bld(const vector<int>& a, int n) {
    for (int i = 0; i < n; ++i) {
        st[i][0] = a[i];
    }

    for (int k = 1; k < K_MAX; ++k) {
        if (!((1 << k) <= n)) break; // 确保区间长度不超过n
        for (int i = 0; i + (1 << k) <= n; ++i) { // 确保区间末尾不越界
            st[i][k] = st[i][k - 1] + st[i + (1 << (k - 1))][k - 1]; // 运算变为 '+'
        }
    }
}

// l, r: 查询区间的左右端点 (0-indexed)
// n: 数组总长度 (用于确定k的最大值，也可不用，直接用K_MAX)
ll qry(int l, int r) { // n 参数在这里实际可以不传入，K_MAX控制上界
    if (l > r) return 0; // 空区间和为0
    ll sum = 0;
    // k 从 K_MAX-1 (即最大可能的 log_2(length)) 开始，确保覆盖所有可能的块大小
    for (int k = K_MAX - 1; k >= 0; --k) {
        if (l + (1 << k) - 1 <= r) { // 如果以l开头，长度为2^k的区间被[l,r]完全包含
                                     // 注意检查 l + (1 << k) 是否会溢出int，但这里k不大，1<<k也不会很大
            sum += st[l][k];
            l += (1 << k); // l指针前进
            if (l > r) break; // 已覆盖整个查询区间 (优化：如果 l == r+1 也行)
        }
    }
    return sum;
}


int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

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

    bld(a, n);

    for (int i = 0; i < m; ++i) {
        int l_idx, r_idx; // 使用不同的变量名以符合规范
        cin >> l_idx >> r_idx; // 假设0-indexed
        cout << qry(l_idx, r_idx) << "\n";
    }
    return 0;
}

复杂度分析:

预处理: 时间, 空间。
查询: 外层循环最多次（因为从递减到）。每次循环。所以查询时间复杂度为。

这种分解方式保证了每个选中的区间都是不重叠的。这是因为当一个长度为的块被选中后，会跳过这个块。

7. ST表的更多应用场景

ST表的多功能性使其能应用于多种满足特定运算性质的区间查询问题。

7.1 区间GCD (最大公约数)

求区间内所有数的最大公约数。
GCD运算满足结合律：。
GCD运算也满足幂等性： (对于非零整数 ; 。通常我们处理正数，或对输入取绝对值)。
因此，ST表可以用于区间GCD查询，预处理，查询。

C++ 代码片段 (预处理与查询核心):
std::gcd 函数在 <numeric> 头文件中 (C++17起)。对于较早标准，可以使用 __gcd (通常在 bits/stdc++.h 中提供)。

// 题意概括: 给定数组a，多次查询区间[l,r]中所有数的最大公约数。
// 全局变量 st 和 lg (同上一部分RMQ)
// int st[N_MAX][K_MAX]; 
// int lg[N_MAX+1];
// (N_MAX, K_MAX 定义同前)

void bld_gcd(const vector<int>& a, int n) {
    // lg 数组预处理 (同RMQ)
    lg[1] = 0;
    for (int i = 2; i <= n; ++i) lg[i] = lg[i/2] + 1;

    for (int i = 0; i < n; ++i) {
        st[i][0] = abs(a[i]); // GCD通常对非负数定义。若a[i]为0, gcd(x,0)=|x|
    }
    for (int k = 1; k < K_MAX; ++k) {
        if (!((1 << k) <= n)) break;
        for (int i = 0; i + (1 << k) <= n; ++i) {
            st[i][k] = std::gcd(st[i][k - 1], st[i + (1 << (k - 1))][k - 1]);
        }
    }
}

int qry_gcd(int l, int r) {
    if (l > r) return 0; // 区间GCD(空集) 可定义为0 (表示任何数都能整除它)，或根据题意
    int len = r - l + 1;
    int k = lg[len];
    return std::gcd(st[l][k], st[r - (1 << k) + 1][k]);
}
// main函数中调用 bld_gcd 和 qry_gcd

注意: 如果数组中可能包含0，。如果所有数都是0，。通常题目会说明数值范围和对0的处理。若输入可能为负数，通常取绝对值后再求GCD。

7.2 区间位运算 (AND, OR, XOR)

按位与 (AND) / 按位或 (OR):
这两个运算都满足结合律和幂等性。

（OR同理）
所以，区间AND和区间OR查询可以使用ST表实现查询。预处理与RMQ(min/max)类似，只需将 min 替换为 & 或 |。
按位异或 (XOR):
XOR运算满足结合律：。
但是XOR不满足幂等性： (除非 )。
因此，区间XOR和查询需要使用的分解策略，类似于区间和。

7.3 ST表与LCA (最近公共祖先)

LCA问题是树结构中的一个经典问题：给定树中的两个节点和，找出它们在树中的最近公共祖先。
ST表可以用来在时间内回答LCA查询，预处理时间为（是树的节点数）。这种方法通常基于将LCA问题转化为RMQ问题。

转化步骤:

欧拉遍历 (Euler Tour) 树: 对树进行一次深度优先搜索 (DFS)。在DFS过程中，记录下每次访问到一个节点（进入时）和每次处理完一个节点的所有子树即将回溯时。这将形成一个序列，我们称之为欧拉序列 (Euler sequence)。
记录深度和节点: 我们需要两个序列：一个是欧拉序列，记录第次访问的节点；另一个是深度序列，记录节点的深度。
记录首次出现位置: 对于树中的每个节点，记录它在欧拉序列中首次出现的位置（下标）。

LCA与RMQ的联系:
对于任意两个节点和，不失一般性地假设。它们在欧拉序列中首次出现的位置分别为和。
考虑深度序列在下标区间内的部分。这个子序列中深度最小的节点就是和的LCA。
这是因为从到的路径在欧拉遍历中，必然会经过。是这条路径上深度最浅的节点。在欧拉序列的段中，所有节点要么是的后代（位于以为根的子树中，路径从到或的部分），要么是本身。因此，是该段欧拉序列对应节点中深度最小的。

实现细节:
DFS遍历树，当第一次访问节点时，将其加入序列，并记录其深度于序列。当从的一个子节点递归返回到后，再次将加入序列，并记录其深度于序列。欧拉序列的长度将是。
ST表将建立在深度序列之上，但存储的是对应最小深度的 原欧拉序列下标，以便最终通过数组取回节点编号。

代码框架 (LCA via RMQ on Euler Tour Depths):

// 题意概括: 给定一棵树，多次查询两点u,v的最近公共祖先。
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int N_MAX = 100005;       // 节点数上限
const int M_MAX = 2 * N_MAX;    // 欧拉序列长度上限 (2N-1 or 2N)
const int K_MAX_LCA = 18;       // log2(M_MAX) approx log2(2e5) = 17.6, so 18 for k up to 17

vector<int> adj[N_MAX]; // 邻接表
int eul[M_MAX];         // 欧拉序列 (存储节点编号)
int dep[M_MAX];         // 对应欧拉序列中节点的深度
int fst[N_MAX];         // fst[u] = 节点u在eul中首次出现的位置
int stl[M_MAX][K_MAX_LCA]; // ST表，存储dep数组中区间最小值的 *下标*
int lgl[M_MAX + 1];     // log数组 (命名为lgl避免与全局lg冲突)

int cnt; // DFS计时器，用于填充eul, dep

void dfs(int u, int p, int d) {
    eul[cnt] = u;
    dep[cnt] = d;
    fst[u] = cnt;
    cnt++;

    for (int v : adj[u]) {
        if (v == p) continue;
        dfs(v, u, d + 1);
        eul[cnt] = u; // 从子节点返回时再次记录父节点
        dep[cnt] = d;
        cnt++;
    }
}

// 比较函数，用于ST表，返回深度较小的那个在eul/dep中的下标
int cmp(int x, int y) { // x, y are indices in eul/dep
    return dep[x] < dep[y] ? x : y;
}

void bld_lca(int n_nodes, int root) { // n_nodes 是树的节点数, root是根节点
    cnt = 0; // 初始化计数器
    dfs(root, 0, 0); // 从根节点开始DFS，深度为0。父节点为0(虚拟)
                     // cnt 最终会是 2*n_nodes - 1 (如果树非空)

    // 预处理log数组 for M_MAX (实际长度是cnt)
    lgl[1] = 0;
    for (int i = 2; i <= cnt; ++i) { 
        lgl[i] = lgl[i / 2] + 1;
    }

    // 初始化 ST 表 stl[i][0]
    for (int i = 0; i < cnt; ++i) {
        stl[i][0] = i; // 存的是dep数组的下标
    }

    // 构建 ST 表
    for (int k = 1; k < K_MAX_LCA; ++k) {
        if (!((1 << k) <= cnt)) break;
        for (int i = 0; i + (1 << k) <= cnt; ++i) {
            stl[i][k] = cmp(stl[i][k - 1], stl[i + (1 << (k - 1))][k - 1]);
        }
    }
}

int qry_lca(int u, int v_node) { // v更名v_node避免冲突
    int l_pos = fst[u];
    int r_pos = fst[v_node];
    if (l_pos > r_pos) swap(l_pos, r_pos); // 保证l_pos <= r_pos

    int len = r_pos - l_pos + 1;
    int k = lgl[len];
    
    int min_dep_idx = cmp(stl[l_pos][k], stl[r_pos - (1 << k) + 1][k]);
    return eul[min_dep_idx]; // 返回的是节点编号
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n, q_cnt; // n节点数, q_cnt查询数
    cin >> n >> q_cnt;

    for (int i = 0; i < n - 1; ++i) {
        int u_node, v_node;
        cin >> u_node >> v_node; // 假设节点1-indexed
        adj[u_node].push_back(v_node);
        adj[v_node].push_back(u_node);
    }
    
    bld_lca(n, 1); // 假设1为根节点

    for (int i = 0; i < q_cnt; ++i) {
        int u_node, v_node;
        cin >> u_node >> v_node;
        cout << qry_lca(u_node, v_node) << "\n";
    }
    return 0;
}

复杂度:

DFS (欧拉序列):
ST表预处理:
单次LCA查询:
空间复杂度: for ST表, for adj, eul, dep, fst. Total .

这是ST表一个非常强大和经典的应用，将图问题巧妙转化为序列RMQ问题。

8. 二维ST表

ST表可以扩展到二维，用于高效查询静态二维矩阵中某个子矩阵的最值（或其他满足结合律和幂等性的运算）。

8.1 思想

给定一个的矩阵。目标是查询任意指定子矩阵到内的最值。
我们定义表示以矩阵位置为左上角，高度为，宽度为的矩形区域内的最值。
其中，, 。
的范围是。
的范围是。

预处理步骤:
预处理过程分为两个主要阶段，总时间复杂度为。

初始化基础单元 ():
对于矩阵中的每个元素，它本身构成一个 (即 ) 的区域。
对所有。
固定行方向幂次，扩展列方向 (计算所有 ):
对每一行，我们独立地计算该行内不同起始点和不同宽度的区间的预处理值。这相当于在每一行上分别构建一个一维ST表。
对于 :
遍历每一行 (从到 )：
遍历列方向的幂次 (从到 )：
遍历起始列 (从到 ):

此步骤完成后，存储了第行，从列开始，宽度为的一维片段的最值。
此阶段的复杂度为。
扩展行方向 (利用上一步结果计算所有 for ):
现在，对于每个已经计算好列向扩展的 (即固定宽度的矩形条带，高度为 )，我们沿行方向进行合并。
遍历行方向的幂次 (从到 ):
遍历起始行 (从到 ):
遍历列方向的幂次 (从到 ):
遍历起始列 (从到 ):

此步骤中，每个状态由两个子状态计算得到，总状态数为。
此阶段的复杂度为。

因此，总的预处理时间复杂度为。
空间复杂度同样为来存储四维的数组。

8.2 查询

查询子矩阵从到的最值。
首先计算查询矩形的高度和宽度。
然后确定覆盖这个高度和宽度的最大的幂次：
（使用预处理的行方向对数数组）
（使用预处理的列方向对数数组）
其中 , 。

查询结果可以通过四个预计算好的大小的子矩形的最值来确定。这四个子矩形共同覆盖了查询区域，并且由于操作的幂等性，它们的重叠部分不影响最终结果。
这四个子矩形的左上角分别是：

对应的查询值为：

,
,
,

单次查询的时间复杂度为。

8.3 C++ 代码实现 (二维RMQ)

// 题意概括: 给定二维矩阵A，多次查询子矩阵[ra,ca]到[rb,cb]的最小值。
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int NMX = 251; // 最大行数 (数组大小，例如250，log数组可能需要NMX)
const int MMX = 251; // 最大列数
const int K1M = 8;   // ceil(log2(NMX-1)) approx 8 (k1最大值7，数组维度8)
const int K2M = 8;   // ceil(log2(MMX-1)) approx 8

int a[NMX][MMX];     // 原始矩阵
int st[NMX][MMX][K1M][K2M]; // ST表
int lgr[NMX + 1], lgc[MMX + 1]; // 对数数组

void bld(int nr, int mc) { // nr:行数, mc:列数
    // 预处理对数数组
    lgr[1] = 0; for (int i = 2; i <= nr; ++i) lgr[i] = lgr[i/2] + 1;
    lgc[1] = 0; for (int i = 2; i <= mc; ++i) lgc[i] = lgc[i/2] + 1;

    // 初始化 st[i][j][0][0]
    for (int i = 0; i < nr; ++i) {
        for (int j = 0; j < mc; ++j) {
            st[i][j][0][0] = a[i][j];
        }
    }

    // 步骤1: 固定k1=0, 沿列方向构建ST表 (填充 st[i][j][0][k2])
    for (int i = 0; i < nr; ++i) { // 遍历每一行
        for (int k2 = 1; k2 < K2M; ++k2) { // k2是列方向块的幂次
            if (!((1 << k2) <= mc)) break; // 确保宽度 2^k2 不超过总列数
            for (int j = 0; j + (1 << k2) <= mc; ++j) { // 起始列j
                st[i][j][0][k2] = min(st[i][j][0][k2 - 1], st[i][j + (1 << (k2 - 1))][0][k2 - 1]);
            }
        }
    }
    
    // 步骤2: 对每个 k1 > 0, 及每个 k2, 沿行方向构建ST表
    // (用 st[...][...][k1-1][k2] 填充 st[i][j][k1][k2])
    for (int k1 = 1; k1 < K1M; ++k1) { // k1是行方向块的幂次
        if (!((1 << k1) <= nr)) break; // 确保高度 2^k1 不超过总行数
        for (int i = 0; i + (1 << k1) <= nr; ++i) { // 起始行i
            for (int k2 = 0; k2 < K2M; ++k2) { // k2是列方向块的幂次
                if (!((1 << k2) <= mc)) break; // 确保宽度 2^k2 不超过总列数 (若k2从小到大, break有效)
                for (int j = 0; j + (1 << k2) <= mc; ++j) { // 起始列j
                     st[i][j][k1][k2] = min(st[i][j][k1 - 1][k2], 
                                           st[i + (1 << (k1 - 1))][j][k1 - 1][k2]);
                }
            }
        }
    }
}

int qry(int ra, int ca, int rb, int cb) {
    int h = rb - ra + 1; // 高度
    int w = cb - ca + 1; // 宽度
    int k1 = lgr[h];     // 对应高度的幂次
    int k2 = lgc[w];     // 对应宽度的幂次

    int m1 = st[ra][ca][k1][k2];
    int m2 = st[ra][cb - (1 << k2) + 1][k1][k2];
    int m3 = st[rb - (1 << k1) + 1][ca][k1][k2];
    int m4 = st[rb - (1 << k1) + 1][cb - (1 << k2) + 1][k1][k2];
    
    return min({m1, m2, m3, m4}); // C++11 initializer_list for min
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int nr, mc, qn; // 行数, 列数, 查询数
    cin >> nr >> mc >> qn;
    for(int i=0; i<nr; ++i) for(int j=0; j<mc; ++j) cin >> a[i][j];

    bld(nr, mc); // 构建二维ST表

    for(int k=0; k<qn; ++k) { // 变量k符合短名称规范
        int ra, ca, rb, cb;
        cin >> ra >> ca >> rb >> cb; // 假设输入为0-indexed
        cout << qry(ra, ca, rb, cb) << "\n";
    }
    return 0;
}

复杂度分析 (二维ST表):

预处理时间复杂度: 。
步骤1（初始化）为。
步骤2（填充）为。
步骤3（填充 for ）的循环层数为，每次内部操作，总共。
因此，总预处理时间为。
查询时间复杂度: 。
空间复杂度: ，用于存储四维数组。
例如，若，则。空间需求个整数。若每个整数4字节，则约16MB，尚可接受。但若，则。空间需求个整数，约400MB，可能超出典型内存限制。

注意:
K1M 和 K2M (代码中表示和的最大幂次值加1，即数组维度) 应设定为 $最大维度$ 。例如，维度250，，最大幂次为7。数组第二维大小为8 (下标 ) 是合适的。

9. ST表与其他数据结构的比较

特性	ST表 (幂等操作)	ST表 (非幂等操作)	线段树	树状数组 (BIT)	分块 (平方分割)
数据类型	静态	静态	动态	动态 (特定操作)	动态 (较慢) / 静态
预处理时间				或
查询时间					或 (特定情况)
修改时间	(完全重建)	(完全重建)			或
空间复杂度			(通常或节点)		或
适用运算	结合律, 幂等性	结合律	结合律	通常可逆运算 (如求和)	灵活，可支持复杂块操作
主要优点	查询极快 (静态幂等)	通用静态区间查询	支持动态修改, 查询/修改较平衡	高效点修改与前缀查询	实现相对简单, 动态性尚可
主要缺点	空间占用大, 数据必须静态	空间占用大, 静态, 查询非最优	查询/修改非	功能受限 (RMQ较复杂)	查询/修改速度相对较慢

选择指南:

数据完全静态，查询操作具有幂等性 (如最值、GCD)，且查询次数非常多: ST表是理想选择，其查询速度极具优势。
数据静态，查询操作不具幂等性 (如求和、异或和)，查询次数多: ST表 ( 查询) 是一种可行方案。但线段树 ( 查询, 空间) 在空间效率上更优。若适中且查询次数极大，ST表的查询可能因常数较小而略快。
数据需要修改: 线段树是标准选择。树状数组适合特定类型的点修改和区间/前缀查询。分块算法在修改和查询复杂度间提供了另一种权衡，有时实现更简便，常数表现也可能不错。
内存限制非常严格: ST表的空间可能成为瓶颈。此时，线段树或分块算法可能是更合适的选择。

10. 解题策略与常见陷阱

10.1 识别何时使用ST表

问题特征识别： 核心标志是处理 静态序列或矩阵 上的 多次区间查询。一旦数据固定，查询频繁，ST表便是候选。
运算性质判断： 查询操作必须满足 结合律。若进一步满足 幂等性 (如取最值、最大公约数)，则可实现查询；否则 (如求和、异或和)，查询复杂度为。
数据规模考量： 对于一维ST表，当序列长度在至级别，且查询次数较大时，的预处理通常可以接受。二维ST表的预处理对的限制更严。
转化应用思维： 一些问题，如树上的最近公共祖先 (LCA)，可以通过欧拉序列等技巧，将其转化为对序列的区间最值查询 (RMQ)，从而利用ST表求解。

10.2 常见陷阱与调试技巧

数组访问越界：
- 数组维度： (表示长度) 的那一维，其大小应为或略大，确保最大可能的值有对应存储空间。例如，若 , ，则最大为16，数组第二维大小至少为17 (若下标从0到16)。
- 循环边界： 预处理时，内层循环的区间起始点必须保证 (对于0-indexed数组，长度为 )，即区间的右端点不超过。
- 查询时下标计算： 计算第二个区间的起始点，如，务必确保该值有效 (非负且在数组范围内)。
对数辅助数组 (lg) 的使用：
- lg[0] 问题： 未定义。lg 数组通常从 lg[1]=0$ 开始填充。查询区间长度 len` 必须大于0。
- 区间长度计算： 区间的长度为。若，则长度为负或零，应特殊处理或确保查询有效。
0-based 与 1-based 索引混淆： 题目输入常为1-based，而C++中 std::vector 和数组习惯用0-based。建议在读入后立即统一转换为0-based进行内部处理，输出时按需转换回去，以减少逻辑错误。
整数溢出： 对于求和、求积等可能产生大数值的运算，若原始数据或中间结果较大，int 类型可能不足以存储，应选用 long long 类型。
幂等性误用： 切忌对不满足幂等性的运算（如求和）直接套用的双区间重叠查询方法。这将导致重叠部分的元素被重复计算，结果错误。
LCA 实现的微妙之处：
- 欧拉序列的构造方式：节点进入DFS、子树返回后等不同时机记录节点，会影响序列内容和长度，进而影响后续RMQ。
- fst 数组（记录节点首次出现位置）的准确性至关重要。
- ST表存储的是深度的值，还是对应最小深度的节点在欧拉序列中的下标。后者更常用，因为最终需要节点编号。
二维ST表的复杂度与资源： 其的预处理时间和空间复杂度非常高。对于较大的，很容易超出时间和内存限制。递推关系的正确实现是关键。

调试核心建议：

小数据手动模拟： 用极小的样例（如或）手动计算出表的每一项，与程序运行结果对比。
打印中间状态： 在预处理和查询的关键步骤打印变量值，特别是表的填充过程、lg 数组的内容、查询时选取的值和两个子区间的端点。
构造边界测试用例： 设计覆盖各种边界情况的测试数据，例如：
- 查询区间长度为1 ()。
- 查询整个数组 ()。
- 查询区间长度恰好为。
- 查询区间的端点在数组的起始或末尾。

10.3 思维扩展与组合应用

ST表与二分答案： 许多求解“最大化最小值”或“最小化最大值”的优化问题，其判定函数（check函数）可能涉及对某个参数进行区间查询（例如，是否存在长度为的子段，其最值满足某种关于的条件）。ST表可以显著加速这种 check 函数，从而优化整个二分答案的流程。
高维ST表： 理论上ST表可以推广到三维甚至更高维度，但预处理时间和空间复杂度将以的连乘形式急剧增长（为各维度大小），实用性大大降低，竞赛中罕见。
持久化ST表： ST表本质上是静态数据结构，不支持高效修改。若问题需要查询历史版本的数据，应考虑使用持久化线段树等专门的持久化数据结构。ST表不适合直接进行持久化改造。

11. 总结

ST表以其优雅的倍增思想，为处理静态序列上的区间查询问题提供了一种高效的解决方案，尤其在操作满足幂等性时，能达到的惊人查询速度。尽管其的空间开销和预处理时间，以及对数据静态性的要求，在一定程度上限制了其应用范围，但在特定场景下，ST表还是非常好用的。

深刻理解其核心原理——倍增策略以及对运算性质（结合律、幂等性）的依赖——是熟练掌握并灵活运用ST表的基石。

附录

例题选讲

洛谷P3865 【模板】ST 表 && RMQ 问题

#include<bits/stdc++.h>
using namespace std;
using ll = long long;


const int MX = 100000;                 // N 上限
const int K  = 17;                     // ⌊log2 1e5⌋ = 16 → 0..16 共 17 层

int lg[MX + 1];                        // 预处理 log2
int st[MX + 1][K + 1];                 // st[i][k] 区间 [i, i+2^k-1] 最大值


int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n, m;                          // 数组长度、询问条数
    if(!(cin >> n >> m)) return 0;

    for(int i = 1; i <= n; ++i){
        cin >> st[i][0];               // 第 0 层即原数组
    }

    /* log 表 */
    lg[1] = 0;
    for(int i = 2; i <= n; ++i) lg[i] = lg[i>>1] + 1;

    /* ST 预处理 */
    for(int k = 1; k <= K; ++k){
        int len = 1 << k;
        if(len > n) break;
        for(int i = 1; i + len - 1 <= n; ++i){
            st[i][k] = max(st[i][k-1], st[i + (len>>1)][k-1]);
        }
    }

    /* 查询并输出 */
    while(m--){
        int l, r; cin >> l >> r;
        int len = r - l + 1;
        int k   = lg[len];
        int ans = max(st[l][k], st[r - (1<<k) + 1][k]);
        cout << ans << '\n';
    }
    return 0;
}

CF1547F Array Stabilization (GCD version)

#include<bits/stdc++.h>
using namespace std;
using ll = long long;


struct ST{
    vector<int> lg;
    vector<vector<int>> sp;
    void build(const vector<int>& v){
        int n = v.size(), K = 32 - __builtin_clz(n);
        lg.resize(n+1); lg[1]=0;
        for(int i=2;i<=n;++i) lg[i]=lg[i>>1]+1;
        sp.assign(K, vector<int>(n));
        sp[0]=v;
        for(int k=1;k<K;++k)
            for(int i=0;i+(1<<k)<=n;++i)
                sp[k][i]=std::gcd(sp[k-1][i], sp[k-1][i+(1<<(k-1))]);
    }
    int qry(int l,int r){            
        int k = lg[r-l+1];
        return std::gcd(sp[k][l], sp[k][r-(1<<k)+1]);
    }
};

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int T; cin>>T;
    while(T--){
        int n; cin>>n;
        vector<int> a(n);
        for(int &x:a) cin>>x;

        bool same=true;
        int G=a[0];
        for(int i=1;i<n;++i){
            if(a[i]!=a[0]) same=false;
            G=std::gcd(G,a[i]);
        }
        if(same){ cout<<0<<"\n"; continue; }

        // 复制一遍方便线性区间 
        vector<int> b(2*n);
        for(int i=0;i<2*n;++i) b[i]=a[i%n];

        ST st; st.build(b);

        auto ok=[&](int len)->bool{
            for(int i=0;i<n;++i)
                if(st.qry(i,i+len)!=G) return false;
            return true;
        };

        int l=0, r=n, ans=n;
        while(l<=r){
            int mid=(l+r)>>1;        // 检查窗口长度 mid+1
            if(ok(mid)){ ans=mid; r=mid-1; }
            else         l=mid+1;
        }
        cout<<ans<<"\n";
    }
    return 0;
}

P2471 [SCOI2007] 降雨量

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

/*----- 预处理 log2 -----*/
const int MAXN = 50000;
int lg2_[MAXN * 2 + 2];

/*----- ST 表：区间最大值 -----*/
struct ST {
    vector<array<int,17>> sp;          // 17 因为 2^16 > 1e5
    void build(const vector<int>& v) {
        int n = v.size();
        sp.assign(n, {});
        for(int i=0;i<n;++i) sp[i][0]=v[i];
        for(int k=1;(1<<k)<=n;++k)
            for(int i=0;i+(1<<k)<=n;++i)
                sp[i][k]=max(sp[i][k-1], sp[i+(1<<(k-1))][k-1]);
    }
    // 最大值 [l,r]  (l≤r)
    int qry(int l,int r){
        if(l>r) return INT_MIN;
        int k=lg2_[r-l+1];
        return max(sp[l][k], sp[r-(1<<k)+1][k]);
    }
};

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    /* log 预处理 */
    lg2_[1]=0;
    for(int i=2;i<(int)sizeof(lg2_)/sizeof(int);++i) lg2_[i]=lg2_[i>>1]+1;

    int n;  cin>>n;
    vector<int> yr(n), rf(n);
    for(int i=0;i<n;++i) cin>>yr[i]>>rf[i];

    ST st; st.build(rf);

    int m; cin>>m;
    while(m--){
        int Y,X; cin>>Y>>X;            // 已保证 Y<X
        // 二分下标
        int idY = lower_bound(yr.begin(),yr.end(),Y)-yr.begin();
        if(idY==n || yr[idY]!=Y) idY=-1;
        int idX = lower_bound(yr.begin(),yr.end(),X)-yr.begin();
        if(idX==n || yr[idX]!=X) idX=-1;

        int mxMid = INT_MIN;
        if(idY!=-1&&idX!=-1 && idY+1<=idX-1)
            mxMid=st.qry(idY+1,idX-1);
        else if(idY==-1&&idX!=-1){
            int l = upper_bound(yr.begin(),yr.end(),Y)-yr.begin();
            if(l<=idX-1) mxMid=st.qry(l,idX-1);
        }
        else if(idY!=-1&&idX==-1){
            int r = lower_bound(yr.begin(),yr.end(),X)-yr.begin()-1;
            if(idY+1<=r) mxMid=st.qry(idY+1,r);
        }
        else{ // both -1
            int l = upper_bound(yr.begin(),yr.end(),Y)-yr.begin();
            int r = lower_bound(yr.begin(),yr.end(),X)-yr.begin()-1;
            if(l<=r) mxMid=st.qry(l,r);
        }

        string ans="maybe";
        if(idY!=-1 && idX!=-1){
            if(rf[idX]>rf[idY] || mxMid>=rf[idX]) ans="false";
            else if(idX-idY==X-Y) ans="true";
        }else if(idX!=-1){              // Y unknown
            if(mxMid>=rf[idX]) ans="false";
        }else if(idY!=-1){              // X unknown
            if(mxMid>=rf[idY]) ans="false";
        }
        cout<<ans<<"\n";
    }
    return 0;
}

题单推荐

ST表专题练习题单

题目名称 (Problem Name)	题号 (ID)	难度/评分 (CF Rating)	ST表应用提示
Ant colony	474F	2100	需要ST表查询区间最小值和区间GCD。之后结合逻辑判断统计等于最小值的元素个数。
Array Partition	1454F	2000	寻找三段划分使得。枚举划分点，ST表快速查询各段最值。
Fools and Roads	191C	2100	树上路径覆盖计数问题。通常解法为LCA + 树上差分。ST表用于高效计算LCA。
Coprime Subsegment	475D	2400	对每个右端点，统计有多少左端点使得区间的GCD为特定值。固定向左扩展时，GCD值种类不多。ST表查GCD，结合二分或双指针。
CGCDSSQ	438D	2400	区间取模、区间求和、单点修改。此题主要用线段树。但若题目变为静态，且查询GCD和SUM，ST表可用于GCD，SUM用 ST表。 (此题主要是线段树，列出是为对比和启发)
The Minimum Number of Variables	343D	2300	树上路径查询与子树修改。常用树链剖分或LCT。若问题简化为静态路径查询（如路径最值），ST表+LCA是基础。 (此题列出作对比和启发)
XOR on Segment	242E	2200	区间XOR和查询，单点修改。用线段树，每个节点维护每一位上1的个数。若为静态区间XOR和，ST表可查询。 (此题列出作对比和启发)
Maximum Submatrix 2 (Harder version of a common theme)	375D	2500+	寻找特定性质的子矩阵。若问题是静态二维RMQ，可用二维ST表。此题本身较复杂，可能涉及DSU on tree或启发式合并。 (列出作二维ST表背景)
Minimum spanning tree for each edge	609E	2300	对于每条非树边，其加入MST后形成的环上权重最大的树边即为需要替换的边。查询树上路径最大值，ST表+LCA。
Range Minimum Query (Problem name is a hint, but the problem might be more complex)	243B	2200-2400	(需具体看题意) 若是纯粹的RMQ或其变种，ST表是直接工具。
Tree Requests	570D	2100	查询子树内某深度的节点形成的字符串能否重排为回文串。预处理每个深度各字符出现次数的奇偶性(用异或哈希)。 DFS序+LCA/ST表可能用于定位子树和深度。