数据结构值ST表的详细讲解浅显易懂

时间：2025-04-07 08:23:46

定义与原理

  • 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表来解决问题。

相关文章