算法总结–ST表

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


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("%d\n",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;
}

4.参考

洛谷ST表模板题题解
本文到此结束,希望对您有所帮助。

原文链接:https://www.cnblogs.com/luokeIT/p/17255225.html

本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:算法总结–ST表 - Python技术站

(0)
上一篇 2023年4月18日
下一篇 2023年4月18日

相关文章

  • C语言单链队列的表示与实现实例详解

    C语言单链队列的表示与实现实例详解 什么是队列? 在计算机科学中,队列(Queue)是一种特殊的数据结构,它只允许在一端进行插入操作,在另一端进行删除操作。将新元素插入队列的过程可以称之为入队,而将元素从队列中删除的过程则可以称之为出队。队列的核心思想是“先进先出”(First In First Out,FIFO),即先入队的元素先出队。 单链队列的表示方式…

    数据结构 2023年5月17日
    00
  • C语言实现通用数据结构之通用链表

    C语言是一门广泛应用于低级别系统编程的语言,也是数据结构和算法学习的重要工具之一,而在C语言中实现通用数据结构的方法之一就是通用链表。 通用链表是一种使用节点来组织数据的通用数据结构,每个节点包含一定量的数据以及指向链表中下一个节点的指针,因此,它可以用来实现许多不同的数据结构,例如栈、队列、树、图、哈希表等等。 具体实现通用链表的方法如下: 步骤一:定义节…

    数据结构 2023年5月17日
    00
  • Python实现计算文件MD5和SHA1的方法示例

    以下是关于“Python实现计算文件MD5和SHA1的方法示例”的完整攻略: 简介 MD5和SHA1是常用的哈希算法,用于计算文件的哈希值。在本教程中,我们将介绍如何使用Python实现计算文件MD5和SHA1的方法,包括使用hashlib库和使用第三方库pycryptodome。 使用hashlib库 hashlib是Python标准库中的一个哈希算法库,…

    python 2023年5月14日
    00
  • Java性能优化之数据结构实例代码

    Java性能优化之数据结构实例代码攻略 本篇攻略主要介绍Java性能优化之数据结构实例代码的相关内容,包括数据结构的优化方法以及示例代码等。我们使用以下两个示例来说明性能优化的过程和方法。 示例1:字符串拼接 在Java中字符串拼接通常使用”+=”方式,但是在循环中频繁地使用该操作会导致性能问题。这时可以使用StringBuilder类的append()方法…

    数据结构 2023年5月17日
    00
  • C语言数据结构之模式匹配字符串定位问题

    C语言数据结构之模式匹配字符串定位问题 什么是模式匹配字符串定位? 模式匹配字符串定位即在一个文本串中匹配一个模式串,并且返回模式串在文本串中第一次出现的位置。 例如,对于文本串“this is a test string”,我们想要匹配模式串“test”,我们期望得到的结果是第一次出现的位置为10。 KMP算法 算法思路 KMP算法是一种高效的字符串匹配算…

    数据结构 2023年5月16日
    00
  • C++中的数组、链表与哈希表

    C++中的数组、链表与哈希表 数组 数组是一种数据结构,它存储的是一组相同类型的值。数组中每个元素的类型都是相同的,而且数组中的元素是按照一定的顺序排列的。C++中的数组是有序的,并且可以通过下标来访问数组中的元素。 数组的定义和初始化 在C++中定义数组的语法如下: type arr_name[arr_size]; 其中,type表示数组元素的类型,arr…

    数据结构 2023年5月17日
    00
  • Java数据结构BFS广搜法解决迷宫问题

    Java数据结构BFS广搜法解决迷宫问题 什么是BFS广搜法? 广度优先搜索(BFS)是一种遍历或搜索数据结构(例如树或图)的算法经典方法之一,也是解决迷宫问题的有效解法之一。BFS方法是从图的某个节点出发,以广度优先的方式依次访问与该节点相通的各节点,直到访问所有节点。BFS算法主要借助队列的数据结构来实现。 解决迷宫问题的具体实现 数据准备: 在解决迷宫…

    数据结构 2023年5月17日
    00
  • Java 超详细讲解数据结构的应用

    Java 超详细讲解数据结构的应用 简介 “Java 超详细讲解数据结构的应用”是一个基于Java语言的数据结构教程,其中包含了各种数据结构的理论知识和实际应用,在学习过程中可以帮助初学者更好地理解数据结构的本质和实际应用场景。 学习路径 数据结构理论 在本教程中,我们首先介绍了数据结构的几种基本分类和常用的数据结构,包括数组、链表、栈、队列、堆、树、图等等…

    数据结构 2023年5月17日
    00
合作推广
合作推广
分享本页
返回顶部