文章目录

稀疏表构造稀疏表查询范围最大值洛谷P3865 ST表

稀疏表

学习稀疏表：https://www.youtube.com/watch?v=c5O7E_PDO4U

稀疏表（Sparse Table），也叫ST表，用来解决范围最值查询（Range Minimum Query）问题。

假设有一个数组，我们需要对该数组执行如下操作（以下全部假设数组下标从0开始）：

求一个区间$[low,high]$内的最大值

不同的解决方法所花的时间不同：

解决方法预处理时间查询时间普通数组$O(1)$$O(n)$动态规划$O(n^2)$$O(1)$线段树$O(n)$$O({\log }_{2}n)$稀疏表$O(n{\log }_{2}n)$$O(1)$

因此，稀疏表在上面4种方式中是最好的。

构造稀疏表

假设数组的大小为$N$。

首先需要一个二维数组$F[N][\lfloor {\log }_{2}N\rfloor +1]$，其中$F[i][j]$表示范围$[i,i+2^i-1]$中的最大值。

例如$F[1][2]$表示范围$[1,4]$中的最大值，即$1$表示从$1$开始，$2$表示$2^2=4$个元素，即下标从1开始的4个元素中的最大值。

构造稀疏表的过程可在$O(n{\log }_{2}n)$时间内完成，思想类似于动态规划。下面是C++的简单实现：

#include <algorithm> int n; int arr[100000]; int sparse_table[100000][17]; void construct_sparse_table() { for (int i = 0; i != n; i++) { sparse_table[i][0] = arr[i]; } for (int j = 1; (1 << j) <= n; j++) { for (int i = 0; i + (1 << j) - 1 < n; i++) { sparse_table[i][j] = std::max(sparse_table[i][j - 1], sparse_table[i + (1 << (j - 1))][j - 1]); } } }

循环中的sparse_table[i][j]可以理解为从$i$开始的$2^j$个元素的最大值。

它等价于在从$i$开始的$2^{j-1}$个元素中的最大值，以及在从$i+2^{j-1}$开始的$2^{j-1}$个元素中的最大值，中的最大的一个值。

即分成两半（因为总共有$2^j$个元素），然后根据这两半的最大值计算最终的最大值。

查询范围最大值

假设范围为$[low,high]$。

令$l=high-low+1$（即范围内的元素个数），$k=\lfloor {\log }_{2}l\rfloor$。

因此只需要找到范围$[low,k]$和$[low+l-2^k,k]$中的最大值即可。

$l-2^k$是因为总共有$l$个元素，已经计算了$2^k$个元素，还差$l-2^k$个元素，这时只需要将范围整体往后移动$l-2^k$即可。

下面是C++的简单实现：

#include <algorithm> #include <cmath> int n; int arr[100000]; int sparse_table[100000][17]; int range_maximum_query(int low, int high) { int l = high - low + 1; int k = static_cast<int>(std::floor(std::log2(l))); return std::max(sparse_table[low][k], sparse_table[low + l - (1 << k)][k]); }

洛谷P3865 ST表

利用这个数据结构，可以解决洛谷P3865 ST表，题目链接：https://www.luogu.com.cn/problem/P3865。

下面是C++的代码：

#include <algorithm> #include <cmath> #include <iostream> int n, m; int arr[100000]; int sparse_table[100000][17]; inline int read() { int x = 0, f = 1; char ch = getchar(); while (!isdigit(ch)) { if (ch == '-') { f = -1; } ch = getchar(); } while (isdigit(ch)) { x = x * 10 + ch - 48; ch = getchar(); } return x * f; } void construct_sparse_table() { for (int i = 0; i != n; i++) { sparse_table[i][0] = arr[i]; } for (int j = 1; (1 << j) <= n; j++) { for (int i = 0; i + (1 << j) - 1 < n; i++) { sparse_table[i][j] = std::max(sparse_table[i][j - 1], sparse_table[i + (1 << (j - 1))][j - 1]); } } } int range_maximum_query(int low, int high) { int l = high - low + 1; int k = static_cast<int>(std::floor(std::log2(l))); return std::max(sparse_table[low][k], sparse_table[low + l - (1 << k)][k]); } int main() { std::cin >> n >> m; for (int i = 0; i != n; i++) { arr[i] = read(); } construct_sparse_table(); int l, r; for (int i = 0; i != m; i++) { l = read(); r = read(); std::cout << range_maximum_query(l - 1, r - 1) << "\n"; } }