算法 ST表

目录

前言

一,暴力法

二,打表法

三,ST表

四,ST表的代码实现 

总结


前言

ST表的主要作用是在一个区间里面寻找最大值,具有快速查找的功能,此表有些难,读者可以借助我的文章和网上的课程结合一起来看,多思考,此文章是逐层深入到ST表,为什么会有ST表,不会直接讲ST表


一,暴力法

问题切入:区间问题求最值

n个数字,在一个区间[ L,R ]中寻找MAX值,此过程进行m次查阅

例子:9 3 1 5 6 0 8

0 ~ 5max为9
4~5max为6

我们不难看出,这个是通过我们人的眼睛扫描最后比较得出得答案,那我们不难写出这个过程的代码

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;int main() {vector<int>arr = { 9,3,1,5,6,0,8 };int ans, L, R;cin >> L >> R;for (int i = L;i <= R;i++) {ans = max(ans, arr[i]);}cout << ans << endl;return 0;
}

我们想一下我们的人眼睛,我们人眼睛扫描一遍是不是需要用for循环遍历一遍,然后大脑不断地进行比对,最终得出最值,此类方法我们称之为暴力法

暴力法:时间复杂度O(nm)

我们不妨把这个复杂度放入到生活中里面实践一下
假设有100个数,同时进行10^7次查找,最后我们地测评集为10^9
1秒里面地测评集合是10^7~10^8,那么这个肯定不行

二,打表法

我们根据上面不难发现时间复杂度是O(nm),那么我们要优化这个时间复杂度的话,不难看出是n和m相差太大了,我们想把这个m换掉,换成小一点的,那么就有了打表法,也就是动态规划的思想
我们是每次选取两个数字,那么不就是利用二项式不就好了

我们这里就是

每次从n个数字选取两个数字,最后就是上面这个结果

我们可以列出表的打法的方程式子

i是左端点,j是右端点

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;int main() {vector<int>arr = { 9,3,1,5,6,0,8 };const int n = 7;vector<vector<int>>ans(n, vector<int>(n, 0));for (int i = 0;i < n;i++) {for (int j = i;j < n;j++) {ans[i][j] = max(ans[i][j - 1], arr[j]);}}int L, R;cin >> L >> R;cout << ans[L][R] << endl;
}

我们看的出来,这个就是一个打印一个表,这个表都有对应得数据,但是我这个代码有个缺陷,就是你刚刚开始得数组不可以为负数,当我们刚刚开始把数字填进去的时候,是与0进行比较填入的,还好这个是容器,会把没有用的空间排出去,要不然就会导致空间浪费,比如我们打一个4*4的表

然后容器就会解决这个问题,类似于边长数组,我们再来计算一下时间复杂度和空间复杂度

时间复杂度:O(n^2+m)
空间复杂度:O(n^2)
我们可以看到这个表的作用是把操作数字和表的行列的数字分开了,不是相乘而是相加,但是当n很大的时候不仅时间炸,这个空间也会炸,所以即使我们利用了表分开,但是结果还是不怎么好,但是我们该怎么利用这个表的思想来进行进一步的优化呢?

三,ST表

这个东西就有点点难,读者请认真理解
ST表也叫稀疏表,是把上面那个表进行稀疏,有些数据不应该要的就不要,有些数据该要才要

按不思想
分析上面那个表的思想:按步思想

然后这个就是每次推断,把每一个可能都写出来

倍增思想
ST表的思想不是这样的,是利用稀疏,也就是倍增思想

不断地取一半取一半就好了,我们拿一个例子把,这样看的更加清晰
我们把这个ST表叫做dp[ i ][ j ]从i开始,长度为2^j的最大值区间

询问操作
[ 0 ][ 5 ]区间找最大值

[ 0 ][ 13 ]区间找最大值

我画了两个不同的图,咋们可以发现什么不,这个其实就是区间的拼凑,拼出一个最大的区间,这个相比较上一个方法其实这个就是类似于一个二分法的方法优化,我下面写的8,4,2其实是想告诉读者这个2^j这个j怎么写,那么不就是[0][3],[8][2],[12][1],可以这么理解,这个i就是左端点的值,这个j就是它的步长

 你以为这个是巧合么?其实并不是,这个其实就是二进制

这个就是那个二进制转十进制公式,是不是很神奇,这个就是运用了这个思想,我们把这个长度(也就是十进制数)转化为二进制数字的和(也就是像后面那样的系数*2的几次方)这个系数不是为1就是0
 

时间复杂度和空间复杂度
我们来计算一下时间复杂度和空间复杂度
时间复杂度:O(m\log_{2}n)
空间复杂度:O(n\log_{2}n)
你别小看这个log,你自己算算就知道这个可以减很多很多,至于这个怎么计算出这个log,我的文章二叉树里面有讲,感兴趣可以取看看

优化\log_{2}n
但其实这个\log_{2}n是可以优化掉的,我为什么要每次都是不重叠呢?我重叠找出的答案都是一样的,那我们重叠的话,那不就是可以减少很多的事情而且答案还是一样的

 这样不是更好么,节省时间复杂度对比0~7和6~13的值就好了,记住这个两个地方的步长都是8,始终记住2^j,这个一定是2的j次方的数字
如何找到那个最长的2的次方的数字呢?我们可以借助log
\log_{2}x这个x是这个区间的长度,我们这样就可以获得对应的长度了
我们利用这个思想的话,有两个情况,一,重合     二,相交


思想
我们用一下思想
长度:len=R-L+1
步长:j=\log_{2}x(x为区间的长度)
最值:ans=max(dp[L][ j ],dp[R-2^j+1][j])
这个里没有听懂没事,我们可以看下面代码再来看这个,这里说没看懂是这个思想上面这个三行

四,ST表的代码实现 

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>using namespace std;vector<vector<int>> dp; // dp[i][j] 表示左端点为 i 长度为 2^j 这样的区间,也就是 [i, i+2^j-1]int query(int l, int r) {int j = (int)log2(r - l + 1);return max(dp[l][j], dp[r - (1 << j) + 1][j]);
}int main() {vector<int> arr = { 9, 3, 1, 7, 5, 6, 0, 8 };const int n = 8;dp = vector<vector<int>>(n, vector<int>((int)log2(n) + 5, 0));for (int i = 0; i < n; i++) dp[i][0] = arr[i];for (int j = 1; j <= log2(n); j++)for (int i = 0; i + (1 << j) - 1 < n; i++)dp[i][j] = max(dp[i][j - 1], dp[i + (1 << (j - 1))][j - 1]);int l, r;while (cin >> l >> r) {cout << query(l, r) << endl;}return 0;
}

这个可能有点难以理解,我们来具体分析一下

容器的定义

dp = vector<vector<int>>(n, vector<int>((int)log2(n) + 5, 0));

这个是构成一个二维的数组利用容器,我这个后面其实不用+5的,这个知识以防万一数组溢出了,所以我就加了个5,然后就是创建一个n*(n+5)的数组,然后初始化为0
为什么是log2(n)呢? 
其实我们前面算出了这个空间复杂度,其实他就是按照步长来的,上面也有十进制转二进制的公式
,然后就是我们这个j本就是表示长度,也就是列,所以我们这么写

情况一

 for (int i = 0; i < n; i++) dp[i][0] = arr[i];

这个是把每一个数字输入到表里面,为了后面的区间的划分建立好基础

情况二

 for (int j = 1; j <= log2(n); j++)for (int i = 0; i + (1 << j) - 1 < n; i++)dp[i][j] = max(dp[i][j - 1], dp[i + (1 << (j - 1))][j - 1]);

这里就是j就是所说的步长了,为什么这个j再外面,而这个i再里面呢?
我们要知道我们再情况一排版的时候,是同列不同行进行排列的,也就是说我们后面编写这个ST表的时候,我们是需要不断地划分区间,就像上面倍增思想那样,那么我们就要这样 

我们是这样取排序的,所以我们就要把这个j放到外面
i表示右端点这个位移大家应该都知道吧,不知道的话我也来讲一讲吧
位移

左移操作符 << 被用来计算2的幂次方。左移操作符将一个数的二进制表示向左移动指定的位数,相当于将该数乘以 2n,其中 n 是移动的位数。

例如,1 << 1 等于 2(十进制的二进制表示是 1,左移一位变成 10,即 2),1 << 2 等于 4(十进制的二进制表示是 1,左移两位变成 100,即 4

为什么这个后面要写成i + (1 << (j - 1))这样子?
其实这个就是我前面所说的i+步长的话,就是找到对对应的数字,然后我们来考虑这个,注意这个是初始化表不是正式区间的最值了,我们这个后面j-1表示对于正在输入列地前面一列,这个i表示步长对对应的值

查询

    int j = (int)log2(r - l + 1);return max(dp[l][j], dp[r - (1 << j) + 1][j]);

这个j呀在这里就是表示长度啦右端点减去左端点+1,为什么要加1?因为有0这个点,长度是会多一个单位的

返回,怎么确定这个行和列呢?

也就是这里的L和R-(1<<j)+1
这里就是表示这个左端点和右端点,然后在这个里面寻找最值

这里就是已经确定这个答案在哪一行了,也就是步长
步长决定这个在哪一列找到
行就是我们之前不是细分了很多下区间吗?我们以1,2,3,4,5,6,7,8为例子讲一下
我们把这个1,2,3,4,5,6,7,8制作为ST表是这样的

我们利用上面的思想我们来找一下1~5的最大值,那就是这样的

我们在小区间里面组成大区间 


总结

我们通过暴力法    打表法    ST表的优化与不优化来讲的
然后就是ST表的实现,主要是怎么打表和查询
打表:
打表主要是先把值都附在表中,然后根据这个表的初始化情况,利用步长来解决,也就是步长为2,4,8,16逐个进行打表
查询:
这里查询主要是逐个列是我们的最大长度,利用log和长度来解决
                                行是利用左端点和右端点,左端点不变,右端点-步长+1,这个+1下面可以解释,我们在计算len,就是区间总长度,为什么不是r-len+1,因为我们有j已经把这个这个定位到后面去了,不是1,2,3,4,5,6,7,8这个了,而是4,5,6,7,8这个,所以我们就要减去2^j才可以正确的解出答案,也就是减去对应得找到那个数字

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/17342.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

node.js+兰空图床实现随机图

之前博客一直用的公共的随机图API&#xff0c;虽然图片的质量都挺不错的&#xff0c;但是稳定性都比较一般&#xff0c;遂打算使用之前部署的兰空图床&#xff0c;自己弄一个随机图 本文章服务器操作基于雨云——新一代云服务提供商的云服务器进行操作&#xff0c;有兴趣的话可…

CNN|ResNet-50

导入数据 import matplotlib.pyplot as plt # 支持中文 plt.rcParams[font.sans-serif] [SimHei] # 用来正常显示中文标签 plt.rcParams[axes.unicode_minus] False # 用来正常显示负号import os,PIL,pathlib import numpy as npfrom tensorflow import keras from tensor…

基于微型5G网关的石化厂区巡检机器人应用

石化工业属于高风险产业&#xff0c;由于涉及易燃易爆、有毒有害工业原料&#xff0c;为了保障企业的安全生产与持续运营&#xff0c;因此相比其它行业需要进行更高频次、更全面细致的安全巡检和监测。由于传统的人工巡检监测存在诸多不便&#xff0c;例如工作强度大、现场环境…

Docker+Jenkins自动化部署SpringBoot项目【详解git,jdk,maven,ssh配置等各种配置,附有示例+代码】

文章目录 DockerJenkins部署SpringBoot项目一.准备工作1.1安装jdk111.2安装Maven 二.Docker安装Jenkins2.1安装Docker2.2 安装Jenkins2.3进入jenkins 三.Jenkins设置3.1安装jenkins插件3.2全局工具配置全局配置jdk全局配置maven全局配置git 3.3 系统配置安装 Publish Over SSH …

知识图谱数据库 Neo4j in Docker笔记

下载 docker pull neo4j:community官方说明 https://neo4j.com/docs/operations-manual/2025.01/docker/introduction/ 启动 docker run \--restart always \--publish7474:7474 --publish7687:7687 \--env NEO4J_AUTHneo4j/your_password \--volumeD:\files\knowledgegrap…

前缀和算法篇:解决子数组累加和问题

1.前缀和原理 那么在介绍前缀和的原理之前&#xff0c;那么我们先来说下前缀和最基本的一个应用场景&#xff0c;那么就是如我们标题所说的子数组累加和问题&#xff0c;那么假设我们现在有一个区间为[L,R]的数组&#xff0c;那么我们要求的其中子数组比如[L,i]或者[i,m] (L&l…

Notepad++ 中删除所有以 “pdf“ 结尾的行

Notepad 中删除所有以 “pdf” 结尾的行 操作步骤 1.打开文件&#xff1a; 在 Notepad 中打开你需要处理的文本文件。 2.打开查找和替换对话框&#xff1a; 按快捷键 Ctrl F&#xff0c;打开“查找和替换”对话框。 3.启用正则表达式模式&#xff1a; 在对话框的底部&#xf…

知识管理成功:关键指标和策略,研究信息的投资回报率

信息过载会影响生产力。没有人工智能的帮助&#xff0c;信息过载会影响生产力。大量的可用信息&#xff0c;知识工作者不仅仅是超负荷工作&#xff1b;他们感到不知所措&#xff0c;他们倾向于浪费时间&#xff08;和脑细胞&#xff09;来应付他们被大量的数据抛向他们&#xf…

Golang 进阶训练营

一、Golang 的 slice、map、channel 1.1 slice vs array a : make([]int, 100) //切片 b : [100]int{} //数组array需指明长度&#xff0c;长度为常量且不可改变 array长度为其类型中的组成部分&#xff08;给参数为长度100的数组的方法传长度为101的会报错&#xff09; array在…

Oracle临时表空间(基础操作)

临时表空间 临时表空间&#xff1a;用来存放用户的临时数据&#xff0c;临时数据在需要时被覆盖&#xff0c;关闭数据库后自动删除&#xff0c;其中不能存放永久性数据。 用户进程和服务器进程是一对一的叫做专用连接。 任何一个用户连到oracle数据库&#xff0c;oracle都会…

AI时代的前端开发:对抗压力的利器

在飞速发展的AI时代&#xff0c;前端开发工程师们面临着前所未有的挑战。项目周期不断缩短&#xff0c;需求变化日新月异&#xff0c;交付压力更是与日俱增&#xff0c;这使得开发人员承受着巨大的压力。如何提升对抗压能力&#xff0c;成为摆在每一位前端工程师面前的重要课题…

如何使用DHTMLX Scheduler的拖放功能,在 JS 日程安排日历中创建一组相同的事件

DHTMLX Scheduler 是一个全面的调度解决方案&#xff0c;涵盖了与规划事件相关的广泛需求。假设您在我们的 Scheduler 文档中找不到任何功能&#xff0c;并且希望在我们的 Scheduler 文档中看到您的项目。在这种情况下&#xff0c;很可能可以使用自定义解决方案来实现此类功能。…

计算机网络-八股-学习摘要

一&#xff1a;HTTP的基本概念 全称&#xff1a; 超文本传输协议 从三个方面介绍HTTP协议 1&#xff0c;超文本&#xff1a;我们先来理解「文本」&#xff0c;在互联网早期的时候只是简单的字符文字&#xff0c;但现在「文本」的涵义已经可以扩展为图片、视频、压缩包等&am…

【pytorch】weight_norm和spectral_norm

apply_parametrization_norm 和spectral_norm是 PyTorch 中用于对模型参数进行规范化的方法&#xff0c;但它们在实现和使用上有显著的区别。以下是它们的主要区别和对比&#xff1a; 实现方式 weight_norm&#xff1a; weight_norm 是一种参数重参数化技术&#xff0c;将权…

回归预测 | Matlab实现PSO-HKELM粒子群算法优化混合核极限学习机多变量回归预测

回归预测 | Matlab实现PSO-HKELM粒子群算法优化混合核极限学习机多变量回归预测 目录 回归预测 | Matlab实现PSO-HKELM粒子群算法优化混合核极限学习机多变量回归预测效果一览基本介绍程序设计参考资料 效果一览 基本介绍 1.回归预测 | Matlab实现PSO-HKELM粒子群算法优化混合核…

多媒体软件安全与授权新范例,用 CodeMeter 实现安全、高效的软件许可管理

背景概述 Reason Studios 成立于 1994 年&#xff0c;总部位于瑞典斯德哥尔摩&#xff0c;是全球领先的音乐制作软件开发商。凭借创新的软件产品和行业标准技术&#xff0c;如 ReWire 和 REX 文件格式&#xff0c;Reason Studios 为全球专业音乐人和业余爱好者提供了一系列高质…

C++,STL容器适配器,stack:栈深入解析

文章目录 一、容器概览与核心特性核心特性速览二、底层实现原理1. 容器适配器设计2. 默认容器对比三、核心操作详解1. 容器初始化2. 元素操作接口3. 自定义栈实现四、实战应用场景1. 括号匹配校验2. 浏览器历史记录管理五、性能优化策略1. 底层容器选择基准2. 内存预分配技巧六…

互联网大厂中面试的高频计算机网络问题及详解

前言 哈喽各位小伙伴们,本期小梁给大家带来了互联网大厂中计算机网络部分的高频面试题,本文会以通俗易懂的语言以及图解形式描述,希望能给大家的面试带来一点帮助,祝大家offer拿到手软!!! 话不多说,我们立刻进入本期正题! 一、计算机网络基础部分 1 …

「软件设计模式」工厂方法模式 vs 抽象工厂模式

前言 在软件工程领域&#xff0c;设计模式是解决常见问题的经典方案。本文将深入探讨两种创建型模式&#xff1a;工厂方法模式和抽象工厂模式&#xff0c;通过理论解析与实战代码示例&#xff0c;帮助开发者掌握这两种模式的精髓。 一、工厂方法模式&#xff08;Factory Metho…

Docker部署Alist网盘聚合管理工具完整教程

Docker部署Alist网盘聚合管理工具完整教程 部署alist初始化修改密码添加存储&#xff01;联通网盘阿里云盘百度网盘 部署alist 本文以Linux Docker部署&#xff0c;假设你已经安装好Docker docker run -d --restartalways \-v /your/data:/opt/alist/data \-p 5244:5244 \-e …