当前位置：首页 > news >正文

009 ST表：静态区间最值的极致优化

news 2025/7/13 21:28:37

ST表（Sparse Table） 是一种解决静态区间最值查询（RMQ） 的高效数据结构。它通过巧妙的倍增思想和动态规划，在O(1)时间内完成查询，成为处理固定数据区间最值问题的利器。

一、ST表核心思想

1. 倍增思想

ST表的核心是倍增预处理：将每个区间的最大值表示为若干长度为 $2^k$ 的子区间最值的组合。

预处理关键步骤：

设f[i][j]表示从位置i开始长度为 $2^j$ 的区间最值
状态转移方程：

 f[i][j] = max(f[i][j-1], f[i + (1 << (j-1))][j-1])

2. 区间查询优化

查询区间[L, R]时，找到满足 $2^k ≤ (R-L+1)$ 的最大k值：

max(f[L][k], f[R - (1 << k) + 1][k])

二、时间复杂度分析

操作	时间复杂度	说明
预处理	O(n log n)	双重循环遍历n个位置和log n个长度
单次查询	O(1)	仅需两次数组访问和取最值操作
空间占用	O(n log n)	二维数组存储所有预处理结果

对比其他数据结构：

线段树：查询O(log n) | 支持动态更新
树状数组：查询O(log n) | 仅部分区间问题
ST表在静态数据场景下性能碾压

三、适用场景与限制

✅ 适用场景：

静态区间最值查询（RMQ）
- 最大值/最小值（最常用）
- 区间GCD
- 区间按位与/或（如[LeetCode 1310]）
结合其他算法优化效率
- LCA问题（欧拉序+RMQ）
- 二维矩阵最值（扩展ST表）
- 分治问题中的快速区间定位

⛔ 使用限制：

数据必须静态：不支持插入/删除操作
可重复贡献：满足f(x,x)=x且f(f(a),f(b))=f(a,b)
空间消耗大：1e6数据需约20n空间

四、模板代码（C++实现）

#include <vector>
#include <cmath>
using namespace std;class ST {vector<vector<int>> f;  // f[i][j]: 从i开始，2^j长度的区间最值vector<int> lg;         // 预计算对数
public:ST(vector<int>& nums) {int n = nums.size();lg.resize(n + 1);// 预处理对数for (int i = 2; i <= n; i++) lg[i] = lg[i >> 1] + 1;// 初始化ST表int k = lg[n] + 1;f.resize(n, vector<int>(k));for (int i = 0; i < n; i++) f[i][0] = nums[i];  // 长度为1的区间// DP计算其他区间for (int j = 1; j < k; j++) for (int i = 0; i + (1 << j) <= n; i++)f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);}int query(int l, int r) {int k = lg[r - l + 1];return max(f[l][k], f[r - (1 << k) + 1][k]);}
};

五、实战应用场景

场景1：快速区间最值（洛谷P3865）

需求：10^6次查询数组固定区间的最大值

ST表解法：

ST st(arr);
while (q--) {cin >> l >> r;cout << st.query(l-1, r-1) << "\n";
}

场景2：区间极差计算（洛谷P2880）

需求：求区间最大/最小值之差

优化方案：

ST max_st(arr);  // 最大值ST表
ST min_st(arr);  // 最小值ST表（需修改query为min）int diff = max_st.query(l, r) - min_st.query(l, r);

场景3：二维最值问题（洛谷P2216）

扩展方案：将ST表扩展到二维

// 伪代码：预处理列方向ST表
for (int k = 1; k < K; k++) for (int i = 0; i < n; i++) for (int j = 0; j <= m - (1<<k); j++) f[i][j][k] = max(f[i][j][k-1], f[i][j+(1<<(k-1))][k-1]);