ST 表：O(1) 查区间最值

数组不修改，只反复查询区间最值：ST 表预存长度为 $1,2,4,8,\ldots$ 的区间，每次查询只取两块。

先把短区间拼成长区间

用零下标，记 $\text{st}[k][i]$ 为从 $i$ 开始、长度为 $2^k$ 的区间最小值。第 0 层就是原数组；之后每一层，把前一层相邻的两块合起来：

\text{st}[k][i]=\min\bigl(\text{st}[k-1][i],\text{st}[k-1][i+2^{k-1}]\bigr).

每层合并相邻的两块，共 $O(\log n)$ 层，预处理的时间、空间都是 $O(n\log n)$ 。

查询为什么可以重叠

查询闭区间 $[l,r]$ ，先选出不超过区间长度的最大二次幂：

k=\lfloor\log_2(r-l+1)\rfloor.

两块长度都为 $2^k$ ，分别贴着左右端点。试着调整下面的区间：

查询式就是：

\min\bigl(\text{st}[k][l],\text{st}[k][r-2^k+1]\bigr).

这要求合并操作满足结合律，而且重复合并同一份信息不改变结果，也就是幂等性。最大值、最小值、GCD、按位与或都可以；求和会重复计算重叠元素，不能直接套这个查询式。数组若会修改，也更适合考虑线段树。

代码

下面只保留建表和查询。约定数组非空，查询使用合法的零下标闭区间；bit_width(len) - 1 就是 $\lfloor\log_2 len\rfloor$ ，不需要浮点运算。代码按 C++20 编译。

展开 ST 表实现与用法

#include <algorithm>
#include <bit>
#include <vector>

template <class T, class Op>
class SparseTable {
    std::vector<std::vector<T>> st;
    Op op;

public:
    SparseTable(const std::vector<T>& a, Op combine) : op(combine) {
        int n = a.size();
        int levels = std::bit_width(static_cast<unsigned>(n));
        st.resize(levels);
        st[0] = a;
        for (int k = 1; k < levels; ++k) {
            int len = 1 << k, half = len / 2;
            st[k].resize(n - len + 1);
            for (int i = 0; i + len <= n; ++i) {
                st[k][i] = op(st[k - 1][i], st[k - 1][i + half]);
            }
        }
    }

    T query(int l, int r) const {
        unsigned len = r - l + 1;
        int k = std::bit_width(len) - 1;
        return op(st[k][l], st[k][r - (1 << k) + 1]);
    }
};

// 用法：
// std::vector<int> a{3, 1, 4, 1, 5, 9, 2, 6};
// SparseTable st(a, [](int x, int y) { return std::min(x, y); });
// st.query(1, 6) == 1;

按一次合并为常数计，查询 $O(1)$ ；GCD 的具体整数运算成本另算。