定义与原理
- ST表，即Sparse Table（稀疏表），是一种基于倍增思想的数据结构。它主要用于在**O(1)**时间复杂度内查询给定区间的最值（最大值或最小值）。其原理是通过预处理，利用倍增的思想，将每个区间的最值信息存储起来，以便后续快速查询。
实现方式
- 预处理：
- 假设有一个长度为n的数组a，我们创建一个二维数组st，其中st[i][j]表示从第i个元素开始，长度为2^j的区间内的最值。
- 初始化时，st[i][0] = a[i]，即长度为1的区间的最值就是元素本身。
- 然后通过动态规划的方式进行递推计算。对于j > 0，st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1])。这表示长度为2j的区间的最值，是由两个长度为2(j - 1)的子区间的最值取较大值（以最大值为例）得到的。
- 查询：
- 当查询区间[i, j]的最值时，我们需要找到一个合适的k，使得2^k尽可能接近区间长度j - i + 1。
- 可以通过计算k = log2(j - i + 1)得到。然后返回max(st[i][k], st[j - (1 << k) + 1][k])。这是因为区间[i, j]可以被拆分成两个重叠的子区间，一个是从i开始长度为2^k的区间，另一个是从j - (1 << k) + 1开始长度为2^k的区间，取这两个子区间的最值即可得到整个区间的最值。
代码示例
以下是用C++ 实现ST表求区间最大值的代码：
#include <iostream>
#include <cmath>
using namespace std;const int N = 100010;
int st[N][20];
int a[N];// 预处理ST表
void init(int n) {for (int i = 0; i < n; i++)st[i][0] = a[i];for (int j = 1; (1 << j) <= n; j++) {for (int i = 0; i + (1 << j) - 1 < n; i++) {st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);}}
}// 查询区间[i, j]的最大值
int query(int i, int j) {int k = log2(j - i + 1);return max(st[i][k], st[j - (1 << k) + 1][k]);
}int main() {int n, m;cin >> n >> m;for (int i = 0; i < n; i++)cin >> a[i];init(n);while (m--) {int l, r;cin >> l >> r;cout << query(l, r) << endl;}return 0;
}
应用场景
- RMQ问题：即Range Minimum/Maximum Query，区间最值查询问题，是ST表最主要的应用场景。例如，在一个数组中频繁查询某个区间内的最大值或最小值。
- 一些需要快速查询区间最值的算法中：如在计算最长公共前缀（LCP）数组等问题中，可以借助ST表来快速获取区间内的最小值等信息，从而优化算法的时间复杂度。
优缺点
- 优点：查询速度快，时间复杂度为O(1)，适用于多次查询静态区间最值的情况。空间复杂度相对较低，为O(nlogn)，其中n是数组的长度。
- 缺点：不支持动态修改数组元素的值，若要修改元素，需要重新进行预处理。预处理的时间复杂度较高，为O(nlogn)，当数据量较大时，预处理时间可能会较长。
ST表是一种在解决区间最值问题上非常有效的数据结构，在许多算法竞赛和实际应用中都有广泛的应用。但在使用时需要根据具体问题的特点来权衡其优缺点，以确定是否适合使用ST表来解决问题。