ST表详解

mouseboy的图书馆 / 2023-09-09 / 原文

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)，因为我们只需进行几次常数级别的操作即可回答查询。

下面是代码实现(以https://www.luogu.com.cn/problem/P3865为例)

 1 #include <iostream>
 2 using namespace std;
 3 const int Maxn = 20;
 4 int a[Maxn][2], dp[Maxn][2], n, m, s;
 5 char c;
 6 int main() {
 7   cin >> n >> m;
 8   for (int i = 1; i <= n; i++) {
 9     for (int j = 0; j <= m + 1; j++) {
10       cin >> c;
11       if (c == '1') {
12         a[i][0] = max(a[i][0], m + 1 - j), a[i][1] = max(a[i][1], j);//求出最左边和最右边
13       }
14     }
15   }
16   dp[n][1] = m + 1;//初始化（应为我们可以确定从初始点走到最右边是 $m+1$ 步）
17   for (int i = n - 1; i >= 1; i--) {
18     for (int j = 0; j <= 1; j++) {
19       dp[i][j] = min(dp[i + 1][!j] + m + 2, dp[i + 1][j] + a[i + 1][!j] * 2 + 1);//求值
20     }
21   }
22   for (s = 1; s < n && !a[s][0]; s++) {
23   }//过滤没灯的那几层
24   cout << min(dp[s][0] + a[s][1], dp[s][1] + a[s][0]);
25   return 0;
26 }