ST表详解

# ST表（Sparse Table）详解

在算法和数据结构中，ST表（Sparse Table）是一种用于解决区间查询问题的数据结构。它可以有效地回答各种形式的查询，例如最小值、最大值、区间和等。

## 简介

ST表的主要思想是通过预处理来加速区间查询。它使用倍增 DP 的思想将一个数组分割成多个子区间，并在每个子区间上计算出某种操作的结果。然后，根据这些预先计算好的结果，我们可以根据需要合并区间来回答各种查询。

具体的实现过程如下：

1. 初始化ST表，ST表是一个二维数组。
2. 将输入的原始数组填充到ST表的第一行。
3. 使用递推关系填充ST表的其他行，直到得到完整的ST表。
4. 根据查询的起始位置和区间长度，在ST表中找到对应区间的值，结合适当的操作得出最终结果。

## 查询操作

对于任何查询操作，我们可以使用以下步骤来回答：

1. 计算出查询区间的长度`len`。
2. 找到大于等于`len`的最大值`j`，使得`2^j <= len`。
3. 使用预处理的结果和递推关系，在ST表中找到对应的值，并结合适当的操作得到查询结果。

这种方法的时间复杂度为O(1)，因为我们只需进行几次常数级别的操作即可回答查询。

下面是代码实现(以[P3865](https://www.luogu.com.cn/problem/P3865)为例)
```cpp
#include <bits/stdc++.h>
using namespace std;

const int Maxn = 1e5 + 5;
int n, m, l, r, dp[Maxn][21], a[Maxn], le[Maxn], len;

int main() {
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
// 输入数组的大小和查询的次数
cin >> n >> m;
// 输入数组的元素
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
le[0] = -1;
// 预处理ST表的第一列
for (int j = 1; j <= n; j++) {
dp[j][0] = a[j];
le[j] = le[j >> 1] + 1;
}
// 填充ST表的其他列
for (int j = 1; (1 << j) <= n; j++) {
for (int i = 1; i + (1 << j) - 1 <= n; i++) {
dp[i][j] = max(dp[i][j - 1], dp[i + (1 << (j - 1))][j - 1]);
}
}
// 处理查询
for (int i = 1; i <= m; i++) {
cin >> l >> r;
len = le[r - l + 1];
cout << max(dp[l][len], dp[r - (1 << len) + 1][len]) << "\n";
}
return 0;
}

```

## 应用场景

ST表在解决各种区间查询问题时非常有用。以下是一些常见的应用场景：

- 查询最小值/最大值：通过选择适当的查询操作，在O(1)的时间复杂度内回答每个查询。
- 区间和查询：可以通过使用累积和来实现区间和查询。
- 区间gcd查询：可以通过预处理和递推关系计算区间内的最大公约数。

## 总结

ST表是一种高效解决区间查询问题的数据结构。通过预先计算和递推关系，我们可以在O(1)的时间复杂度内回答各种形式的查询。它的实现相对简单且灵活，适用于多种应用场景。

希望这篇博客对你理解ST表有所帮助！如果有任何问题，请随时向我提问。