稀疏表(ST表)
组别：提高级
难度：6
稀疏表(Spare table表)主要是应用倍增法思想，用来解决区间最值查询问题(RMQ: range Minimum/Maximum query) ，并且在空间和时间复杂度方面具有较好的性能。稀疏表主要应用于静态数组，即数组在构建之后不再发生变化的场景。以下是稀疏表的一些关键特点和基本原理：
对于一个长度为n的数组询问区间最值，S。
有下列n个元素的数组arr={3,7,1 ,6,8 ,2 ,0,4,9,5}，想计算m次任意区间的最大值
方法一：暴力枚举算法
对于每个查询区间进行搜索查询，算法复杂度O(nm)，n为元素个数，m为查询次数。当m特别大的时候，此方法表现比较差。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | /**************************************************************** * Description: C++ implementation of RMQ by emuerations * Author: Alex Li * Date: 2023-06-13 15:33:36 * LastEditTime: 2023-06-13 15:42:13 ****************************************************************/ #include <iostream> #include <limits> using namespace std; int main(){ int arr[]={4,9,0,1,2,5,6,3,8,7}; int answer,left,right; while(cin>>left>>right) { answer=INT_MIN; //initialize answer every query for (int i =left; i<=right; i++)answer=max(answer,arr[i]); cout<<answer<<endl; } } |
方法二：打表法
事先将answer[i][j]做好，查询时直接调用。算法复杂度O(n2+m)
answer[i][i]=arr[i];
answer[i][j]=max(answer[i][j-1],arr[j])
代码实现：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 | /**************************************************************** * Description: C++ implementation of sparse table * Author: Alex Li * Date: 2023-06-12 19:05:32 * LastEditTime: 2023-06-12 19:59:53 ****************************************************************/ #include <iostream> using namespace std; int main(){ int arr[]={3,7,9,6,8,2,0,4,1,5}; int ans[10][10]; for (int i = 0; i <10; i++){ for (int j = i; j <10;j++){ if(i==j)ans[i][j]=arr[i]; else ans[i][j]=max(ans[i][j-1],arr[j]); } } int left,right; while(cin>>left>>right){ cout<<ans[left][right]<<endl; } return 0; } |
方法三：利用倍增构建ST表
任意整数均可表示为若干个2的次幂项之和。例如10进制的任何整数，都可以转化成2进制形式。
ST（Sparse Table，稀疏表）算法采用了倍增思想，在O (n logn)时间构造一个二维表之后，可以在O (1)时间在线查询[l , r ]区间的最值，有效解决在线RMQ（Range Minimum/Maximum Query，区间最值查询）问题。
ST表实现： 设 F[i][j] ，它表示[i, i+2j-1]区间的最值，区间长度为2j
根据 倍增思想，长度为2j的区间可被分成两个长度为2j-1的子区间，然后求两个子区间的最值即可。
递推公式：F[i][j]=max(F[i][j-1], F[i+2j-1][j-1])
ST表的建立
若数组长度为n，最大区间长度2k<=n<2k+1，
比如，n=8时，k=3。 n=13时，k=3。
以数组arr={3,7,1 ,6,8 ,2 ,0,4,5,9}为例，创建查询最大值的ST表
F[i][j]表示[i, i+2j-1]区间的最值，区间长度为2j
ST表查询
若查询[l, r]区间的最值，则首先计算k值，和前面的计算方法相同，区间长度为r-l+1， 2k<=r-l+1<2k+1，因此k=log2(r-l+1)
若查询区间的长度大于或等于2K且小于2k+1，则根据倍增思想，可以将查询区间分为两个查询区间，取两个区间的最值即可。
两个区间分别为从l向后的2k个数，及r向前的2k个数。这两个区间可能重叠，但对求结果没有影响。
ST预处理的时间为O(nlogn)，查询时间为O(1)，不支持在线修改。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 | #include <iostream> #include <cmath> using namespace std; int F[10][4]; // 稀疏表，用于存储区间信息 // 创建稀疏表 void createST(int *a, int n) { // 初始化稀疏表的第一列 for (int i = 0; i < n; i++) F[i][0] = a[i]; // 计算稀疏表其他列 int k = log2(n); // 计算最大可能的列数 for (int j = 1; j <= k; j++) { for (int i = 0; i <= n - (1 << j); i++) // 确保索引不越界 F[i][j] = max(F[i][j-1], F[i + (1 << (j-1))][j-1]); // 填充稀疏表 } } // 查询区间 [l, r] 内的最大值 int queryST(int l, int r) { int k = log2(r - l + 1); // 计算区间长度的对数值 return max(F[l][k], F[r - (1 << k) + 1][k]); // 返回区间最大值 } int main() { int arr[10] = {3, 7, 1, 6, 8, 2, 0, 4, 5, 9}; // 初始化数组 createST(arr, 10); // 创建稀疏表 int l, r; cin >> l >> r; // 输入查询区间 cout << queryST(l, r); // 输出区间最大值 } |