【数据结构:线性表】倍增表(ST表)

这篇具有很好参考价值的文章主要介绍了【数据结构:线性表】倍增表(ST表)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

知识点

一 . 基本概念

ST表:又名稀疏表,用来处理区间最值查询离线算法,用到了倍增的思想

某个区间查询问题是否适用ST表,关键在于其进行的操作是否允许区间重叠。

例如max(a,b,c) = max{max(a,b),max(b,c)}就可以用ST表维护,而区间和问题则不能维护。

在时间复杂度上:预处理时间O(nlogn),单词查询O(1),时间复杂度:O(nlogn+m) 。

二 . 实现方式

设二维数组f[i][j]代表从i号位置开始往后推个单位长度的区间里的最大值,即【数据结构:线性表】倍增表(ST表)区间的最大值

① 预处理

【数据结构:线性表】倍增表(ST表)

这里要注意更新顺序,因为其中 j (第二维)才是阶段,而第一维 x 是状态,所以对于 j 的循环要放在最外层。

【数据结构:线性表】倍增表(ST表)

 【数据结构:线性表】倍增表(ST表)

② 查询

当查询任意区间的最大值时,先计算出指数k,满足不等式【数据结构:线性表】倍增表(ST表),将该不等式同时转换为以为底的数:【数据结构:线性表】倍增表(ST表),可得:k为当前小于区间长度且能满足2的k次幂的值最大的数。

 文章来源地址https://www.toymoban.com/news/detail-515058.html

左端点:num[l][l+2^k-1]

右端点:num[r-2^k+1][r]

注意这里的的表示方法:(1<<k)=pow(2,k)=

!!位运算优先级很低但是运算速度快,需要加括号


模板题

例题: 洛谷 P3865 【模板】ST 表 / 洛谷 P1816 忠诚

题目背景

这是一道 ST 表经典题——静态区间最大值(静态RMQ问题)

题目描述

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

输入格式

第一行包含两个整数 N,M,分别表示数列的长度和询问的个数。

第二行包含 N 个整数(记为 ),依次表示数列的第 i 项。

接下来 M 行,每行包含两个整数 ,表示查询的区间为 。

输出格式

输出包含 M 行,每行一个整数,依次表示每一次询问的结果。

输入输出样例

输入 #1

8 8
9 3 1 7 5 6 0 8
1 6
1 5
2 7
2 6
1 8
4 8
3 7
1 8

输出 #1

9
9
7
7
9
8
7
9

说明/提示

对于 30% 的数据,满足 。

对于 70% 的数据,满足 。

对于 100% 的数据,满足 ,,,。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#define re register
using namespace std;
const int maxn=1e5+5;
int f[maxn][21];
int n,m;
inline int read()  //快读模板
{
    re int x=0,f=1;
    re char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=(x<<3)+(x<<1)+ch-'0';
        ch=getchar();
    }
    return x*f;
}

inline int rmq(int l,int r)
{
    re int k=log2(r-l+1); 
        //如果2k+1<=r-l+1
        //while (1<<(k+1)<=r-l+1) ++k; 同样的效果
    return max(f[l][k],f[r-(1<<k)+1][k]);
}

int main()
{
    n=read(),m=read();
    for(re int i=1;i<=n;++i)
    {
        f[i][0]=read();
    }

    for(re int j=1;j<=21;++j)
    {
        for(re int i=1;i+(1<<j)-1<=n;++i)
        {
            f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
        }
    }

    for(re int i=1;i<=m;++i)
    {
        re int g=read(),b=read();
        printf("%d\n",rmq(g,b));
    }
    return 0;
}

相关练习

1 .  洛谷 P1440 求m区间内的最小值

 朴素ST表(80pts):会存在两个数据MLE。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define ll long long 
#define re register
using namespace std;
int n,m,t;
const int maxn=2e7+5;
int a[maxn],f[maxn][21];
inline int read()
{
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9')
	{
		if(c=='-') f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9')
	{
		x=(x<<3)+(x<<1)+(c^48);
		c=getchar();
	}
	return x*f;
}

inline void ST() //ST表预处理
{
	for(re int i=1;i<=n;++i)
	{
		f[i][0]=a[i];
	}
	for(re int j=1;j<=20;++j)
	{
		for(re int i=1;i+(1<<j)-1<=n;++i)
		{
			f[i][j]=min(f[i][j-1],f[i+(1<<(j-1))][j-1]);
		}
	}
}

inline int query(int l,int r) //ST表查询
{
	int k=log2(r-l+1);
	return min(f[l][k],f[r-(1<<k)+1][k]); //要注意这里r-(1<<k)+1的写法,不要写漏东西
}

int main()
{
	n=read(); m=read();
	for(re int i=1;i<=n;++i)
	{
		a[i]=read();
	}
	ST();
	for(re int i=1;i<=n;++i)
	{
		re int l=i-m,r=i-1;
		if(r<1) //第一个数据输出为0
		{
		printf("0\n");	
		continue;
		} 
		if (l<1) l=1;
             //如果查询的范围大到超出i之前的所有数,从边界1开始处理
		printf("%d\n",query(l,r));
	}
	return 0;
}

(待填坑)滚动数组优化

我不会。。。

2 . 洛谷 P2251 质量检测

该题注意查询部分:第 i 行的数表示 Q[i + M - 1] 即可。

 

到了这里,关于【数据结构:线性表】倍增表(ST表)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构选择题练习知识点整理【3】

    n 个点连通且无环的简单无向图为连通图,连通则至少有n-1条边,无环则只有n-1条边。n个点连通且无环的简单无向图有n-1条边,非零个数为2(n-1),零元素个数为n^2-2(n-1)。得出零元素个数为n²-2n+2。 算术表达式 中缀、前缀、后缀的互相转换 中-前 从右到左 数字入栈,碰见运算

    2024年02月06日
    浏览(52)
  • Java面试知识点(全)-数据结构和算法

    Java面试知识点(全)https://nanxiang.blog.csdn.net/article/details/130640392 注:随时更新 数组 数组的下标寻址十分迅速,但计算机的内存是有限的,故数组的长度也是有限的,实际应用当中的数据往往十分庞大;而且无序数组的查找最坏情况需要遍历整个数组;后来人们提出了二分查

    2024年02月05日
    浏览(62)
  • 数据结构之双链表的相关知识点及应用

     找往期文章包括但不限于本期文章中不懂的知识点: 个人主页 :我要学编程(ಥ_ಥ)-CSDN博客 所属专栏 :数据结构 目录 双链表的实现  初始化双链表  在双链表中尾插数据  在双链表中尾删数据 在双链表中头插数据  在双链表中头删数据  在双链表中的指定位置之后插入

    2024年04月26日
    浏览(53)
  • 数据结构中一些零碎且易忘的知识点

    第一章 绪论 数据结构包含三个方面的内容: 数据的逻辑结构:描述数据之间逻辑关系的、与数据的存储无关的数学模型。相同的逻辑结构可使用不同的存储结构存储,如线性表既可顺序存储,也可链式存储 线性结构:一个线性表是n个具有相同特性的数据元素的有限序列 一

    2024年02月14日
    浏览(41)
  • 数据结构之单链表的相关知识点及应用

     找往期文章包括但不限于本期文章中不懂的知识点: 个人主页 :我要学编程(ಥ_ಥ)-CSDN博客 所属专栏 :数据结构 目录 链表的概念及结构 链表与顺序表的区别与优劣势 链表的分类 单链表的实现 单链表中增加节点  单链表中尾插数据  打印单链表中节点的数据  单链表中

    2024年04月15日
    浏览(38)
  • C#学习笔记--数据结构、泛型、委托事件等进阶知识点

    ArrayList 元素类型以Object类型存储,支持增删查改的数组容器。 因而存在装箱拆箱操作,谨慎使用。 ArrayList和数组区别? ArrayList使用不用说明固定长度,数组则需要 数组存储的是指定类型的,ArrayList是Object ArrayList存在装箱拆箱,数组不存在 ArrayList数组长度用Count获取 而数组

    2024年02月08日
    浏览(50)
  • 【数据结构】考研真题攻克与重点知识点剖析 - 第 6 篇:图

    本文基础知识部分来自于b站:分享笔记的好人儿的思维导图与王道考研课程,感谢大佬的开源精神,习题来自老师划的重点以及考研真题。 此前我尝试了完全使用Python或是结合大语言模型对考研真题进行数据清洗与可视化分析,本人技术有限,最终数据清洗结果不够理想,

    2024年04月15日
    浏览(53)
  • 软考知识点——数据结构:大顶堆与小顶堆、哈夫曼树

    目录 一、大顶堆与小顶堆 1.大顶堆与小顶堆的概念 2.大顶堆的构建 二、哈夫曼树 1.哈夫曼树的定义 2.基本概念 3.构造哈夫曼树 4.哈夫曼编码 大顶堆:每个结点的值都大于或等于其左右孩子结点的值。 小顶堆:每个结点的值都小于或等于其左右孩子结点的值。 以数组A=(2,

    2024年02月06日
    浏览(39)
  • 【数据结构入门精讲 | 第十六篇】并查集知识点及考研408、企业面试练习

    上一篇中我们进行了散列表的相关练习,在这一篇中我们要学习的是并查集。 在许多实际应用场景中,我们需要对元素进行分组,并且在这些分组中进行查询和修改操作。比如,在图论中,我们需要将节点按照连通性进行分组,以便进行最小生成树、最短路径等算法;在计算

    2024年02月03日
    浏览(51)
  • 【算法与数据结构】二叉树的三种遍历代码实现(上)—— 用递归序知识点讲解

      本篇博客 (上篇) 先带大家学习 递归方式 进行三种遍历, 而在后续的 (下篇) 中将为大家详细讲解非递归的三种遍历方式。 目录 1、二叉树 2、二叉树的递归遍历 2.1、先序遍历 2.2、中序遍历 2.3、后序遍历  二叉树(Binary tree)是树形结构的一个重要类型。许多实际问

    2024年02月08日
    浏览(44)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包