【算法】倍增-ST表

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

一.倍增

【算法】倍增-ST表,基本算法,算法

 倍增是一种常用的算法技巧,通常用于优化时间复杂度。它的核心思想是将原问题分解成若干个规模较小的子问题,通过对子问题的求解来得到原问题的解。具体来说,倍增算法通常采用二分思想,将问题规模不断缩小,直到问题规模足够小,可以直接求解。

在计算机科学中,倍增算法通常用于解决一些需要快速求解的问题,例如最近公共祖先、区间最大值、区间和等问题。通过采用倍增算法,可以将这些问题的时间复杂度从O(n)降低到O(logn),从而大大提高算法的效率。


二.ST表 

【算法】倍增-ST表,基本算法,算法

 ST表(Sparse Table)是一种用于解决区间查询问题的数据结构。它可以在O(1)的时间复杂度内回答区间最值查询问题,如区间最大值、最小值等。

ST表的构建过程是基于动态规划的思想。首先,我们需要预处理出一个二维数组dp,其中dp[i][j]表示从位置i开始,长度为2^j的区间内的最值。然后,通过递推的方式,我们可以得到dp数组的所有值。

构建ST表的时间复杂度为O(nlogn),其中n是原始数组的长度。一旦ST表构建完成,我们可以在O(1)的时间内回答任意区间的最值查询。

ST表的应用非常广泛,特别是在解决静态区间查询问题时非常有效。例如,在解决最长公共前缀、区间最大值、区间最小值等问题时,ST表都可以提供高效的解决方案。

需要注意的是,ST表适用于静态数据,即查询操作多而修改操作少的情况。如果数据是动态变化的,需要频繁进行修改操作,那么ST表可能不是最优的选择,可以考虑其他数据结构,如线段树。

 


三.模板题

P3865 【模板】ST 表 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)


四.参考代码

#include<bits/stdc++.h>
#define maxn 100005
using namespace std;

int f[maxn][30];
int n,m;
int query(int l,int r){
	int k=log2(r-l+1);
	return max(f[l][k],f[r+1-(1<<k)][k]);
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%d",&f[i][0]);
	//初始化 
	for(int j=1;(1<<j)<=n;j++){
		for(int i=1;i<=n+1-(1<<j);i++){
			f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
		}
	}
	for(int i=1;i<=m;i++){
		int l,r;
		scanf("%d%d",&l,&r);
		printf("%d\n",query(l,r));
	}
	return 0;
}

五.范围解释

【算法】倍增-ST表,基本算法,算法

 

(1)j的范围:

因为j为长度,显然长度不能大于n,即(1<<j)<=n;

(2)i的范围

因为长度为1<<j,所以n-i+1<=1<<j。 然后移项即可

【算法】倍增-ST表,基本算法,算法

 尽可能取最大长度,f[r+1-(1<<k)][k]是由有边界为r,长度为1<<k推出来的。文章来源地址https://www.toymoban.com/news/detail-675746.html

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

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

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

相关文章

  • STM32-基本知识梳理10-FSMC控制ST7789V-LCD液晶显示屏

    一、ST7789V-LCD液晶显示 1,一种计算机的I/O设备,即输入输出设备; 2,数据传递结构,光线的传递通过偏光片进行调整,最终传递到滤光片上,进而不同RGB数据点,即像素点; 3, LCD显示器的关键参数 ①像素:显示器的像素指它成像最小的点 ②分辨率:像素点的个数的乘积

    2024年02月12日
    浏览(48)
  • 【图论】LCA(倍增)

    LCA通常指的是“最近共同祖先”(Lowest Common Ancestor)。LCA是一种用于解决树或图结构中两个节点的最低共同祖先的问题的算法。 在树结构中,LCA是指两个节点的最近层级的共同祖先节点。例如,考虑一棵树,其中节点A是节点B和节点C的祖先,而节点D是节点B和节点C的共同祖

    2024年02月15日
    浏览(30)
  • 15 个非常流行的VsCode插件,让你的编码效率倍增!

    VS Code已经成为了最受欢迎的代码编辑器之一。 它的简洁性、易用性和可扩展性使得它成为了许多开发者的首选。 而在VS Code中,插件是其最大的卖点之一。 通过安装插件,你可以将VS Code打造成一个功能强大的开发环境,从而提高你的编码效率。 本文中,将介绍15个非常流行

    2024年02月06日
    浏览(53)
  • 优酷路由宝不拆机回刷 实现金币倍增的详细教程

    高手亲测,不用拆机,回刷优酷路由宝,实现金币倍增! 1、以回刷到固件1.5.0211.47252为例,先刷好。不会的可参考我的另一篇经验。这里不再啰嗦! 2、刷好后,用网页登陆路由器(192.168.11.1),点击\\\"路由设置\\\",修改网址中“admin/wifiset”为“api/devices/allowConnect?mac=%3Bpasswd%20-d

    2024年02月08日
    浏览(54)
  • lc 1483 树节点的第 K 个祖先(树上倍增、动态规划)

    lc 1483 树节点的第 K 个祖先 我们定义:节点的第 i 级 父节点为第 2 i 2^i 2 i 个 父节点 规律1: 节点的第 n 个父节点 = 节点的第 n i n_i n i ​ 个父节点的第 n j n_j n j ​ 个父节点,其中 n i + n j = n n_i+n_j=n n i ​ + n j ​ = n 。 (倍增) 以 二进制 为基础,节点 i 的 第 2 j 2^j 2 j 个父

    2024年04月28日
    浏览(34)
  • elasticsearch[一]-索引库操作(轻松创建)、文档增删改查、批量写入(效率倍增)

    在 elasticsearch 提供的 API 中,与 elasticsearch 一切交互都封装在一个名为 RestHighLevelClient 的类中,必须先完成这个对象的初始化,建立与 elasticsearch 的连接。 分为三步: 1)引入 es 的 RestHighLevelClient 依赖: 2)因为 SpringBoot 默认的 ES 版本是 7.6.2,所以我们需要覆盖默认的 ES 版本

    2024年01月16日
    浏览(61)
  • 【树上倍增】【内向基环树】【 图论 】2836. 在传球游戏中最大化函数值

    树上倍增 内向基环树 图论 给你一个长度为 n 下标从 0 开始的整数数组 receiver 和一个整数 k 。 总共有 n 名玩家,玩家 编号 互不相同,且为 [0, n - 1] 中的整数。这些玩家玩一个传球游戏,receiver[i] 表示编号为 i 的玩家会传球给编号为 receiver[i] 的玩家。玩家可以传球给自己,

    2024年04月17日
    浏览(41)
  • 2023年清洁电器行业数据分析:洗地机市场规模持续倍增,进入赛点

    洗地机作为清洁电器领域的明星品类,正在成为继扫地机器人之后拉动清洁电器市场大盘的又一核心动力。 在清洁电器领域,扫地机器人、洗地机和吸尘器是三大热门品类。截至今年9月份,根据鲸参谋平台的数据显示,吸尘器的规模继续大幅下滑,销量同比降低约19%,销额

    2024年02月07日
    浏览(55)
  • 第三章 图论 No.3 flody之多源汇最短路,传递闭包,最小环与倍增

    flody的四个应用: 多源汇最短路 传递闭包 找最小环 恰好经过k条边的最短路 倍增 多源汇最短路:1125. 牛的旅行 1125. 牛的旅行 - AcWing题库 直径概念:同一连通块中,两个距离最远的点之间的距离 如何求直径?由于图中存在着两个连通块,所以直接对全图做一个flody,就能更

    2024年02月14日
    浏览(45)
  • 11.动态规划:树形DP问题、树上最大独立集、树上最小支配集、换根DP、树上倍增(LCA)【灵神基础精讲】

    回溯和树形DP的区别(什么时候需要return结果?):对于回溯,通常是在「递」的过程中增量地构建答案,并在失败时能够回退,例如八皇后。对于递归,是把原问题分解为若干个相似的子问题,通常会在「归」的过程中有一些计算。如果一个递归能考虑用记忆化来优化,就

    2024年02月04日
    浏览(42)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包