ST 表（sparse table）是一个基于 （链接未公开） 思想的数据结构，可用于可重复贡献子问题静态查询的数据结构。

RMQ 问题的 ST 表

区间最值查询（Range Max/Min Query, RMQ）问题是 ST 表的经典应用，可以在 O(1) 时间内返回一个区间的最大值或最小值。以下问题以最大值为例。

思路

可重复贡献的性质，允许我们将查询区间拆成重叠的子区间，例如，查询数组 [a_1, \dots, a_n] 在区间 [1, 7) 的最小值时，可以拆成区间 [1, 5) 和 [3, 7)，重叠部分不影响最终结果，只要区间的并是原区间即可。

由此我们引出了 ST 表的思想：预处理所有长度为 2 的幂的区间中的最大值，也就是利用倍增方法。我们开一个长为 n、第二维最大下标为 h 的二维数组 st[h + 1][n]（注意第一维的下标从 0 开始计数），其中 2^{h - 1} < n \le 2^h，则由于 h = O(\log n)，这个数组占用的空间是 O(n \log n) 级别的。

然后我们让元素 st[i][j] 表示以第 i 个元素 a_i 为起点、长为 2^j 的区间 [i, i + 2^j) 也就是 [i, i + 2^j - 1] 中元素的最大值。st[j][i] 代表的区间 [i, i + 2^j) 可以“从中间劈开”，变成两个小区间 [i, i + 2^{j - 1}) 和 [i + 2^{j - 1}, i) ，它们的长度都是 2^j，刚好就是 st[j - 1][i] 和 st[j - 1][i + 2^{j - 1}] 两个元素。因此，这个表的每个元素都可以由下层的两个元素合并得到：

查询时，如果我们要查询 [l, r) 区间，只需要令 h = \lfloor \log_2 (r - l) \rfloor，然后返回

ST 表的特点

• ST 表的各个高度的数组并不等长，第 h 层只有 n - 2^h + 1 个节点
• 当区间长度恰好为 2 的幂 2^h 时，一般仍然处理为两个长为 2^h 区间查询的合并，而不是 2^{h - 1}
  • 这样做可以避开特判长度为 1 的区间
  • 此时，当原始数组恰好有 n = 2^m 时，ST 表最顶层将有一个只有单元素的数组。

复杂度

时间复杂度：预处理 O(n \log n)，查询 O(1) 空间复杂度：O(n \log n)

代码

竞赛风格

#include <iostream>
#include <cstring>
using namespace std;

constexpr size_t MAXN = 1e5 + 5, MAXH = 30;
int a[MAXN], st[MAXH][MAXN];
size_t lg2[MAXN] = {0, 0};

void init_log(size_t n)
{
    for (size_t i = 2; i <= n; i++)
    {
        lg2[i] = lg2[i / 2] + 1;
    }
}

void build_st(size_t n)
{
    size_t h = lg2[n];

    memcpy(st[0] + 1, a + 1, sizeof(int) * n);
    // for (size_t i = 1; i <= n; i++)
    // {
    //     st[0][i] = a[i];
    // }
    for (size_t j = 1; j <= h; j++)
    {
        for (size_t i = 1; i + (1u << j) - 1 <= n; i++)
        {
            st[j][i] = max(st[j - 1][i], st[j - 1][i + (1u << (j - 1))]);
        }
    }
}

// [l, r)
int rmq(size_t l, size_t r)
{
    int j = lg2[r - l];
    return max(st[j][l], st[j][r - (1u << j)]);
}

类封装

要求 C++20，需要 #include <bit>

class SparseTable {
public:
    SparseTable(const vector<int> &a)
    {
        const size_t n = a.size();
        size_t h = log2(n);
        st.reserve(h + 1);
        st.push_back(a);
        for (size_t j = 1; j <= h; j++)
        {
            size_t len = n - (1u << j) + 1;
            st.push_back(vector<int>(len));
            for (size_t i = 0; i < len; i++)
            {
                st[j][i] = max(st[j - 1][i], st[j - 1][i + (1u << (j - 1))]);
            }
        }
    }

    // [l, r)
    int query(size_t l, size_t r)
    {
        size_t h = log2(r - l);
        return max(st[h][l], st[h][r - (1u << h)]);
    }

private:
    vector<vector<int>> st;

    size_t log2(size_t x)
    {
        return __bit_width(x) - 1;
    }
};

一般区间问题

ST 表也可以用于维护其他静态数组的区间查询问题。在问题不可重复贡献时，ST 表单次查询的复杂度将增大到 O(\log n)。

维护不可差分数据的区间和，可以使用 ST 表以 O(n \log n) 预处理、O(\log n) 查询，也可以使用线段树 O(n) 预处理、O(\log n) 查询。不过，ST 表查询时的常数更小。

应用

ST 表的运算

可重复贡献子问题

一般而言，ST 表维护的运算，要求重复贡献不影响结果。例如求区间 [1, 6] 的最大值 s[1, 6] 时，若 [1, 4] 和 [3, 6] 两段区间的最大值已求出，则 s[1, 6] = \max(s[1, 4], s[3, 6])。这里虽然区间 [3, 4] 对答案重复贡献了两次，但不影响正确性，拥有这种特性的问题称为可重复贡献子问题。

也就是说，ST 表维护的运算 \circ 需要有结合律，且对任意元素 x 满足幂等性，即 x \circ x = x。这种运算在数学上被称为带（band）。多数时候，这种运算还满足交换律，此时称为半格。

满足半格条件的运算有最大值、最小值、按位与、按位或、最大公因数、最小公倍数等。

半格与最小上界

若 \le 是 S 上的偏序关系，则可以定义 x = \sup(\{u, v\}) 为 u \le x, v \le x，且对任意 y \le S，若 u \le y, v \le y 则 x \le y 的元素 x。

若一个偏序集 (S, \le) 中的任意两元素都存在上确界，则可以验证 u \circ v := \sup( \{ u, v \} ) 是一个半格运算；反之，若根据半格运算定义 a \le b \Leftrightarrow a \circ b = b，则可以验证 (S, \le) 存在上确界。因此，半格的一种等价定义是存在上确界的偏序集。

因此，查询区间最小上界或最大下界的操作就是一类可重复贡献子问题。例如，对 32 位整数的按位或可以视为求 32 维偏序的最小上界，求最大公因数可以看作求整除关系的最大下界，也就是标准分解式中的逐指数取最小值。

例题

• CF Round 900 (Div.3) E. Iva & Pay