ST 表：静态区间最值查询｜算法讲义

问题#

给定一个之后不再修改的数组，多次查询半开区间 $[l,r)$ 的最小值。

前缀和能快速处理区间和，却不能通过两个前缀最小值恢复区间最小值。ST 表预处理所有长度为 $2^k$ 的区间答案，再用至多两个预处理区间覆盖询问。

核心思想#

定义：

\text{st}[k][i] =\min(a_i,a_{i+1},\ldots,a_{i+2^k-1}),

即从 $i$ 开始、长度为 $2^k$ 的区间最小值。

转移时把一个长度 $2^k$ 的区间分成两个长度 $2^{k-1}$ 的区间：

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

查询长度 $L=r-l$ 时，取 $k=\lfloor\log_2 L\rfloor$ 。区间 $[l,l+2^k)$ 与 $[r-2^k,r)$ 一定能覆盖整个询问，二者可能重叠：

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

不变量#

st[k][i] 始终准确表示 $[i,i+2^k)$ 的最小值。构建按 $k$ 从小到大进行，因此计算第 $k$ 层时，两段第 $k-1$ 层答案已经存在。

为什么存在幂等限制#

两个查询区间可能重叠，所以合并运算必须允许重复贡献：

x\operatorname{op}x=x.

最小值、最大值、最大公约数、按位与、按位或满足这一性质；加法不满足。因此普通 ST 表不能用两个重叠区间求区间和。

复杂度#

预处理时间： $O(n\log n)$
单次查询： $O(1)$
空间： $O(n\log n)$
不支持低复杂度在线修改；数组变化后需要重建

可独立编译的 C++17 模板#

模板回答非空半开区间 $[l,r)$ 的最小值。空区间没有最小值，因此被视为非法。

#include <algorithm>
#include <cstddef>
#include <iostream>
#include <stdexcept>
#include <vector>

class SparseTableMin {
public:
    explicit SparseTableMin(const std::vector<long long>& values)
        : size_(values.size()),
          log2_(size_ + 1, 0) {
        if (size_ == 0) {
            return;
        }

        for (std::size_t length = 2; length <= size_; ++length) {
            log2_[length] = log2_[length / 2] + 1;
        }

        const int level_count = log2_[size_] + 1;
        table_.assign(
            static_cast<std::size_t>(level_count),
            std::vector<long long>(size_)
        );
        table_[0] = values;

        for (int level = 1; level < level_count; ++level) {
            const std::size_t length =
                std::size_t{1} << static_cast<unsigned int>(level);
            const std::size_t half = length / 2;

            for (
                std::size_t left = 0;
                left + length <= size_;
                ++left
            ) {
                table_[static_cast<std::size_t>(level)][left] =
                    std::min(
                        table_[static_cast<std::size_t>(level - 1)][left],
                        table_[static_cast<std::size_t>(level - 1)]
                              [left + half]
                    );
            }
        }
    }

    long long query(
        std::size_t l,
        std::size_t r
    ) const {
        if (l >= r || r > size_) {
            throw std::out_of_range("query must be a non-empty range");
        }

        const std::size_t length = r - l;
        const int level = log2_[length];
        const std::size_t block_length =
            std::size_t{1} << static_cast<unsigned int>(level);

        return std::min(
            table_[static_cast<std::size_t>(level)][l],
            table_[static_cast<std::size_t>(level)]
                  [r - block_length]
        );
    }

private:
    std::size_t size_;
    std::vector<int> log2_;
    std::vector<std::vector<long long>> table_;
};

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n = 0;
    int query_count = 0;
    std::cin >> n >> query_count;
    if (n <= 0) {
        return 0;
    }

    std::vector<long long> values(static_cast<std::size_t>(n));
    for (long long& value : values) {
        std::cin >> value;
    }

    const SparseTableMin sparse_table(values);
    while (query_count-- > 0) {
        std::size_t l = 0;
        std::size_t r = 0;
        std::cin >> l >> r;
        std::cout << sparse_table.query(l, r) << '\n';
    }
}

示例#

输入：

7 4
5 2 6 3 1 7 4
0 7
1 4
3 6
6 7

输出：

例如查询 $[1,4)$ 时，区间长度为 3，选取两段长度 2 的区间 $[1,3)$ 与 $[2,4)$ 。它们在位置 2 重叠，但最小值重复参与不会改变答案。

易错点#

把空区间传给查询： $\log_2 0$ 没有定义，RMQ 查询必须非空。
混用闭区间：模板使用 $[l,r)$ ，长度为 $r-l$ 。
浮点计算对数：直接调用浮点 log2 可能产生精度问题，模板预处理整数对数表。
构建越界：只构建满足 $i+2^k\le n$ 的状态。
误用于区间和：两个块可能重叠，非幂等运算会重复计算。
尝试在线更新：普通 ST 表是静态结构；有修改时考虑树状数组或线段树。

边界测试#

单元素数组与长度 1 查询。
$n$ 不是 2 的幂。
查询长度恰为 2 的幂，以及比它多 1。
查询整个数组、首段、尾段。
数组严格递增、严格递减、全部相等、含负数。
对小数组枚举所有 $0\le l<r\le n$ ，与逐元素取最小值对拍。

变体#

区间最大值：把 std::min 改为 std::max。
GCD、按位与、按位或：它们同时满足结合律和幂等性，可直接替换合并函数。
同时维护最大值与最小值：每个状态保存一个二元组。

问题#