题解 | #【模板】静态区间最值#

这是一个非常经典的ST表（Sparse Table）模板题。ST表是一种基于倍增思想（Binary Lifting）和动态规划的数据结构，专门用于解决静态区间最值查询（RMQ - Range Minimum/Maximum Query）问题。

它的特点是：

• 构建耗时：
• 查询耗时： （极快）
• 适用场景：数组构建后不再修改，且需要大量查询区间最值（Max, Min, GCD等）。

核心思想——倍增法

朴素的做法是遍历区间 ，时间复杂度 ，如果有 次询问，总时间 ，对于 的数据量会超时。

ST 表的核心思想是：我们不存储所有可能的区间结果，只存储长度为 的整数次幂的区间结果。

即，我们只记录长度为 的区间最值。

状态定义（预处理）

我们需要两个二维数组（因为题目同时要求最大值和最小值）：

• st_max[i][j]：表示从下标 开始，长度为 的区间内的最大值。
• st_min[i][j]：表示从下标 开始，长度为 的区间内的最小值。

区间的范围是：。

1. 初始状态（长度为 ）

长度为 1 的区间最大/最小值就是元素本身。

2. 状态转移（如何计算更长的区间）

要把长度为 的区间算出来，我们可以把它平分成两段长度为 的区间：

• 左半段：从 开始，长度 。即 st[i][j-1]。
• 右半段：从 开始，长度 。即 st[i + (1<<(j-1))][j-1]。

转移方程：

图解： 计算区间 [1, 8] (长度8) 的最大值，等于 max([1, 4], [5, 8])。

区间查询

假设我们要查询区间 的最值。区间长度 。 这个长度 可能不是 2 的幂次（比如长度是 6）。

ST 表的神奇之处在于：求最值允许区间重叠。 例如：。中间的 被计算了两次，但不影响结果。

查询策略：

1. 找到一个最大的整数 ，使得 。通常 。
2. 用两个长度为 的区间覆盖整个 ：
   • 左边一段：从 开始向右 。即 st[l][k]。
   • 右边一段：以 结尾向左 （即从 开始）。即 st[r - 2^k + 1][k]。
3. 取两者的最值。

查询公式：

代码实现

为了达到严格的 查询，我们需要预处理 log2 的值，否则每次调用 std::log2 函数可能会比较慢。

预处理 Log 数组： Log[i] 表示 。 递推公式：Log[i] = Log[i/2] + 1。

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

class SparseTable {
  private:
    // 根据题目 N <= 5*10^5，LOGN = ceil(log2(N))
    static constexpr int LOGN = 20;
    vector<vector<ll>> stMin;
    vector<vector<ll>> stMax;
    // 预处理 log2 值，用于 O(1) 查询中确定区间长度对应的 k
    vector<int> logTable;
    int n;

    void initLogTable() {
        if (n == 0)
            return;
        logTable.resize(n + 1);
        logTable[1] = 0;
        for (int i = 2; i <= n; i++) {
            logTable[i] = logTable[i / 2] + 1;
        }
    }

    void build(const vector<ll>& a) {
        if (n == 0)
            return;

        stMin.assign(n, vector<ll>(LOGN));
        stMax.assign(n, vector<ll>(LOGN));

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

        for (int j = 1; j < LOGN; j++) {
            // i 的范围：i + 2^j - 1 < n
            for (int i = 0; i + (1 << j) - 1 < n; i++) {
                // 左半部分：i, 长度 2^(j-1)
                int left = i;
                // 右半部分：i + 2^(j-1), 长度 2^(j-1)
                int right = i + (1 << (j - 1));
                stMin[i][j] = min(stMin[left][j - 1], stMin[right][j - 1]);
                stMax[i][j] = max(stMax[left][j - 1], stMax[right][j - 1]);
            }
        }
    }

  public:
    explicit SparseTable(const vector<ll>& a): n(a.size()) {
        initLogTable();
        build(a);
    }

    ll queryMin(ll l, ll r) {
        if (l > r || r >= n) {
            throw std::out_of_range("Invalid range for query.");
        }
        int len = r - l + 1;
        int k = logTable[len];

        return min(stMin[l][k], stMin[r - (1 << k) + 1][k]);
    }

    ll queryMax(ll l, ll r) {
        if (l > r || r >= n) {
            throw std::out_of_range("Invalid range for query.");
        }
        int len = r - l + 1;
        int k = logTable[len];

        return max(stMax[l][k], stMax[r - (1 << k) + 1][k]);
    }
};


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

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

    // 构建 ST 表
    SparseTable st(a);

    while (q--) {
        int op;
        int l, r;
        cin >> op >> l >> r;
        l--;
        r--;
        if (op == 1) {
            cout << st.queryMin(l, r) << endl;
        } else if (op == 2) {
            cout << st.queryMax(l, r) << endl;
        }
    }
}