算法总结–ST表

技术分享 3年前 (2023-03-26) 0 999+

声明(叠甲)：鄙人水平有限，本文为作者的学习总结，仅供参考。

1. RMQ 介绍

在开始介绍 ST 表前，我们先了解以下它以用的场景 RMQ问题。RMQ (Range Minimum/Maximum Query)问题是指：对于长度为n的数列A，回答若干询问RMQ(A,i,j)(i,j<=n)，返回数列A中下标在i,j里的最小(大）值，也就是说，RMQ问题是指求区间最值的问题，其主要的特征是查询的区间是静态的。
在上一篇关于线段树的文章中我们解决了动态的区间的维护，先是进行O(nlog(n))时间负载度的建树预处理，然后就能以O(log(n))的时间复杂度进行维护与查询。对于 RMQ 问题来说线段树也是能过比较好的处理，总的时间复杂度为O(nlog(n)+log(n)),比暴力法的时间复杂O(n^2)还行快一些。

2. ST 表介绍

虽然线段树也能比较好的解决 RMQ 问题，但是它的特性还是更加符合动态的情况，故对于静态的来说就引入了 ST 表来进行解决。ST 表是先对数据进行 O(nlog(n)) 的预处理，然后就可以进行 O(1) 的查询。(是常数！！！)
故，一般的 ST 表题的解法解法可以分为以下步骤：

【1】进行预处理，一般来说使用动态规划的思想进行的
【2】进行查询

3. 举些栗子

3.1 ST 表模板题

题目描述

给定一个长度为 N 的数列，和 M 次询问，求出每一次询问的区间内数字的最大值。

这是一道 ST 表经典题——静态区间最大值，根据上述的描述，解题思路如下（具体的数学关系就不做解释，自己画画图就可以推理出来的）：

【1】 进行预处理 ：这里我们使用一个数组 st[i][j] 进行打表，其含义为从第 i 个数开始数 2^j 个数中的最大值，故我们可以得到动态规划的状态转移方程：                         st[i][j] = max(st[i][j-1],st[i-(1<<j)][j-1]) 【2】 进行查询 : 对于区间 [l,r] 来说，我可以使用以下来表达其的最大值：                                     m = log2(r-l+1)                         max[l,r] = max(st[l][m],st[r-(1<<m)][m])

根据以上的思路可以得到以下代码

#include <bits/stdc++.h> using namespace std; #define NMAX 100000 int n,m,x,y; int st[NMAX+1][20]; // st[i][j] 表示从 i 开始 2^j 个数中需要的答案  // ST 表的查询函数 int calc(int l,int r) { 	int m = log2(r - l + 1); 	return max(st[l][m],st[r-(1<<m)+1][m]);	 }  int main() { 	// [1] 获取数据并进行预处理 	cin >> n >> m; 	for(int i = 1;i <= n;++i) 	{ 		cin >> st[i][0]; 	}       // 需要注意的是我们要从 i 开始遍历 st[i][j] 	for(int j = 1; (1 << j) <= n;++j) 	{ 		for(int i = 1;i + (1<<j) - 1 <= n;++i) 		{ 			st[i][j] = max(st[i][j-1],st[i + (1<<(j-1))][j-1]); 		} 	} 	// [2] 查询 	while(m--) 	{ 		scanf("%d%d",&x,&y); 		printf("%dn",calc(x,y));	 	}      return 0; }

3.2 质量检测

题目描述

为了检测生产流水线上总共 N 件产品的质量，我们首先给每一件产品打一个分数 A 表示其品质，然后统计前 M 件产品中质量最差的产品的分值 Q[m] = min{A_1, A_2, ... A_m}，以及第 2 至第 (M + 1) 件的 Q[m + 1], Q[m + 2] ... 最后统计第 N - M + 1 至第 N 件的 Q[n]。根据 Q 再做进一步评估。

请你尽快求出 Q 序列。

解题思路如下

总的思路如上题一致，无非就是从查询最大最变成了最少小值，以及查询时给定了区间左右边界的规定关系 [i,i+M-1]
具体 AC 代码如下

#include <bits/stdc++.h>  #define NMAX 1000000 using namespace std;  int m,n; int st[NMAX+1][32];  int calc(int x,int y) { 	int m = log2(y-x+1); 	return min(st[x][m],st[y-(1<<m)+1][m]); }  int main() { 	cin >> n >> m; 	// [1] 获取数据，并进行预处理 	for(int i = 1;i <= n;i++) 	{ 		cin >> st[i][0];	 	}  	for(int j = 1;(1<<j) - 2<= n;j++) 	{ 		for(int i = 1;i+(1<<j)-1 <= n;i++) 		{ 			st[i][j] = min(st[i][j-1],st[i+(1<<(j-1))][j-1]);	 		}	 	}	 	// [2] 查询 	for(int i = m;i <= n;i++) 	{ 		cout << calc(i-m+1,i) << endl; 	} 	 	return 0; }

3.3 [蓝桥杯 2022 省 A] 选数异或

题目描述

给定一个长度为 n 的数列 A1 A2 ... An 和一个非负整数 x, 给定 m 次查询, 每次询问能否从某个区间 [l, r] 中选择两个数使得他们的异或等于 x

这题一眼看出就是很明显的静态区间查询问题，但是与上述中不同的是，这次查询的不再是最值，而是满足关系数对的下标。

总的解题思路还是不变的：

【1】预处理：这里的两数异或我们可以联想到两数和的问题，故可以利用一个 Hash 数组记录其每个数的下标来辅助我们处理（具体实现见代码），需要注意的是我 ST 表中记录的应该是与这个数满足关系对象中的最近一个,故状态转移方程为：st[i] = max(st[i-1],Hash[Ai])
【2】根据预处理得到的 ST 表，我们只要查表看该区间得到的值是否大于区间的左边界值

AC 代码如下：

#include <bits/stdc++.h> using namespace std;  int main() {     int n,m,x; 	cin >> n >> m >> x; 	map<int,int> Hash;     // st[i] 表示 1~i 中满足关系的数对的最后出现的一个的下标 	int st[n+1] = {0,};     // [1] 预处理     for(int i = 1;i <= n;i++)     {         int data;         cin >> data;         st[i] = max(st[i-1],Hash[data]);         Hash[data^x] = i;     }     // [2] 查询     while(m--)     {         int l,r;         cin >> l >> r;         if(st[r] >= l) cout << "yes" << endl;         else cout << "no" << endl;     }     return 0; }