【算法】差分思想:强大的算法技巧
📢博客主页:https://blog.csdn.net/2301_779549673
📢欢迎点赞 👍 收藏 ⭐留言 📝 如有错误敬请指正!
📢本文由 JohnKi 原创,首发于 CSDN🙉
📢未来很长,值得我们全力奔赴更美好的生活✨


文章目录
- 📢前言
- 🏳️🌈一、差分思想概述
- 🏳️🌈二、差分思想的优缺点
- 🏳️🌈例题题解
- 👥总结
📢前言
大家可以先看一下题目


由于随着订单数量的增加,每天可用教室的数量一定单调下降。
因此我们可以二分出最后一天没出现负值的订单编号。
剩下的问题是如何快速求出经过若干订单后,每天所剩的教室数量。
每个订单的操作是 [Li,Ri]全部减去 di
因此我们可以用差分来加速处理过程。
🏳️🌈一、差分思想概述
在 C++ 中,差分思想主要涉及差分数组和原数组的关系。差分数组也是一个数组,定义为 d [ i ] = a r r [ i ] − a r r [ i − 1 ] ( i ! = 0 ) d[i] = arr[i] -arr[i-1](i != 0) d[i]=arr[i]−arr[i−1](i!=0),且 d [ i ] = 0 d[i] = 0 d[i]=0,其中 arr[] 即为原数组。例如,有原数组 :9 3 5 2 7,对应的差分数组 :9 -6 2 -3 5。可以看出,差分数组的第一个值等于原数组第一个值,而其他位置的值等于原数组对应位置的值减去前一个位置的值。
差分数组的精髓在于可以通过其前缀和得到原数组。假设差分数组为 b ,原数组为 a ,那么 a [ i ] = b [ i ] + a [ i − 1 ] a[i] = b[i] + a[i-1] a[i]=b[i]+a[i−1] 比如,若 i=1 ,那 a[1] = b[0] + b[1] ;
若 i=2 ,那 a[2] = b[0] + b[1] +b[2];
通过这种关系,可以利用差分数组在 O(1) 的时间复杂度内将区间内的元素都加上某个数。例如输入一个长度为 n 的整数序列,有频繁区间修改操作时,如让第 1 个数到第 1000 万个数每个数都加上 1,如果采用暴力方法遍历区间,时间复杂度是 O(n) ,效率非常低。
而使用差分数组,只需要对差分数组中的两个位置进行修改即可实现区间修改,大大降低了时间复杂度O(1)。比如,在区间 [l,r] 上所有的数值都加上常数 c ,只需要将 b[l] = b[l] + c ,然后在 b[r+1] = b[r+1] - c ,这样就把一连串的循环遍历修改 转变为了对两个位置数字的修改 ,效率大大提升。
🏳️🌈二、差分思想的优缺点
差分思想在多个方面展现出显著的优势。
首先,在简化运算方面,差分数组能够将对区间元素的复杂操作转化为对差分数组中特定位置的简单修改。例如,当需要给一个区间 [l,r] 上的数组加一个常数 c 时,传统方法需要依次遍历区间内的每个元素进行加法操作,时间复杂度为 O(n) 。而利用差分数组,只需对差分数组中的两个位置进行修改,即 b[l] = b[l] + c 和 b[r+1] = b[r+1] - c ,时间复杂度降低至 O(1) 。这种简洁高效的操作方式在处理大规模数据和频繁的区间修改操作时优势尤为明显。
其次,在提高效率方面,对于包含大量区间修改操作的场景,C++ 差分思想能够极大地提高程序的执行效率。以处理长度为 n=100000 的整数序列为例,假设有 m=1000 个操作,每个操作都是对一个区间进行修改。如果使用传统方法,每次操作都需要遍历区间内的元素,总的时间复杂度将高达 O(m * n) 。而采用差分数组,每次操作只需要对两个位置进行修改,总的时间复杂度降低为 O(m + n) 。通过对比可以看出,差分数组在处理大量区间修改操作时效率提升巨大。
然而,差分思想也并非完美无缺。
虽然使用差分思想优化了区间的修改效率,使其变成了一个常数级的操作,但对原数组的访问效率却受到了一定的影响。因为对原数组中某个元素的访问需要通过差分数组的前缀和来计算,时间复杂度变为了 O(i) 。例如,当需要获取原数组中第 i 个元素的值时,需要计算差分数组中前 i 项的和,这在一定程度上增加了访问原数组的时间成本。
综上所述,C++ 差分思想在简化运算和提高效率方面具有明显优势,但在访问原数组时也存在一定的局限性。在实际应用中,需要根据具体情况权衡利弊,选择合适的方法来处理数据。
🏳️🌈例题题解
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<iostream>
#include<cstring>using namespace std;typedef long long LL;
const int N = 1000001;int n, m;
int r[N];
int d[N], s[N], t[N];
LL e[N];bool check(int mid)
{memset(e, 0, sizeof(e));for (int i = 1; i <= mid; i++){e[s[i]] += d[i];e[t[i] + 1] -= d[i];}for (int i = 1; i <= n; i++){e[i] += e[i - 1];if (e[i] > r[i])return false;}return true;
}int main()
{scanf("%d%d", &n, &m);for (int i = 1; i <= n; i++){scanf("%d", &r[i]);}for (int i = 1; i <= m; i++){scanf("%d%d%d", &d[i], &s[i], &t[i]);}int L = 0, R = m;while (L < R){int mid = L + (R - L + 1) / 2;if (check(mid))L = mid;elseR = mid -1;}if (R == m)printf("%d", 0);elseprintf("%d\n%d", -1, R + 1);
}
👥总结
本篇博文对 差分思想 做了一个较为详细的介绍,不知道对你有没有帮助呢
觉得博主写得还不错的三连支持下吧!会继续努力的~

相关文章:
【算法】差分思想:强大的算法技巧
📢博客主页:https://blog.csdn.net/2301_779549673 📢欢迎点赞 👍 收藏 ⭐留言 📝 如有错误敬请指正! 📢本文由 JohnKi 原创,首发于 CSDN🙉 📢未来很长&#…...
微软开源项目 Detours 详细介绍与使用实例分享
目录 1、Detours概述 2、Detours功能特性 3、Detours工作原理 4、Detours应用场景 5、Detours兼容性 6、Detours具体使用方法 7、Detours使用实例 - 使用Detours拦截系统库中的UnhandledExceptionFilter接口,实现对程序异常的拦截 C++软件异常排查从入门到精通系列教程…...
Numba基础
1. Numba 基础 1.1 什么是 Numba? Numba 是一个 JIT 编译器,用于加速数值计算。它通过即时编译技术,将 Python 代码在运行时编译为机器代码,极大地提升执行速度,特别适合循环和矩阵操作等密集型计算。 2. Numba 基本…...
[JAVA]介绍怎样在Java中通过字节字符流实现文件读取与写入
一,初识File类及其常用方法 File类是java.io包下代表与平台无关的文件和目录,程序中操作文件和目录,都可以通过File类来完成。 通过这个File对象,可以进行一系列与文件相关的操作,比如判断文件是否存在,获…...
oracle停止当前运行的JOB或kill会话
在Oracle中,可以使用DBA_SCHEDULER_JOBS视图来查找当前正在运行的作业(job),并使用DBMS_SCHEDULER.STOP_JOB过程来停止它们 SELECT JOB_NAME, STATE FROM DBA_SCHEDULER_JOBS WHERE STATE RUNNING; SELECT * FROM DBA_SCHEDULE…...
SpringBoot 消息队列RabbitMQ 消息可靠性 数据持久化 与 LazyQueue
介绍 在默认情况下,RabbitMQ会将接收到的信息保存在内存中以降低消息收发的延迟 一旦MO宕机,内存中的消息会丢失内存空间有限,当消费者故障或处理过慢时,会导致消息积压,引发MQ阻塞 在消息队列运行的过程中…...
CLIP论文中关键信息记录
由于clip论文过长,一直无法完整的阅读该论文,故而抽取论文中的关键信息进行记录。主要记录clip是如何实现的的(提出背景、训练数据、设计模式、训练超参数、prompt的作用),clip的能力(clip的模型版本、clip…...
sshj使用代理连接服务器
之前我是用jsch连接服务器的,但是没办法使用私钥连接,搜了一下似乎是不支持新版的SSH-rsa,并且jsch很久没更新了,java - "com.jcraft.jsch.JSchException: Auth fail" with working passwords - Stack Overflow 没办法…...
【Leetcode:1184. 公交站间的距离 + 模拟】
🚀 算法题 🚀 🌲 算法刷题专栏 | 面试必备算法 | 面试高频算法 🍀 🌲 越难的东西,越要努力坚持,因为它具有很高的价值,算法就是这样✨ 🌲 作者简介:硕风和炜,…...
VRRP 笔记
一、概念: vrrp:Virtual Router Redundancy Protocol 虚拟路由冗余协议,当网关发生故障时,进行主备切换,保证业务连续性 把多台物理机的网关虚拟成一台Virtual Router,称为 VRID VIP:虚拟IP VM…...
【洛谷】P3743 小鸟的设备 的题解
【洛谷】P3743 小鸟的设备 的题解 题目传送门 题解 水一道二分 qaq 刚开始考虑的是动态规划,但是动态规划并不能维护题目所要求的东西。所以我们将思路转向另一种求最值问题的方法:二分答案。 首先,如果一个设备在 t t t 的时间内消耗的…...
算法面经手撕系列(2)--手撕BatchNormlization
BatchNormlization BatchNormlization的编码流程: init阶段初始化 C i n C_in Cin大小的scale向量和shift向量,同时初始化相同大小的滑动均值向量和滑动标准差向量;forward时沿着非channel维度计算均值、有偏方差依据得到均值和有偏方差进…...
mysql-搭建主从复制
文章目录 1、准备主服务器2、准备从服务器3、主库配置3.1、创建MySQL主服务器配置文件: 4、从库配置5、搭建主从&测试5.1、使用命令行登录MySQL主服务器5.2、主机中查询master状态:5.3、从机中查询slave状态:5.4、主机中创建slave用户&am…...
MiniMaxi-共创智能新体验新手入门
新手快速入门 注册指南 个人用户 直接注册即可。 企业团队 主账号:注册时填写的姓名与手机号将成为企业账号的管理员。子账号:在用户中心创建,数量不限。 主账号与子账号权益 相同权益:子账号享有与主账号相同的使用权益和速…...
Docker torchserve 部署模型流程
1.拉取官方镜像 地址: https://hub.docker.com/r/pytorch/torchserve/tags docker pull pytorch/torchserve:0.7.1-gpu2. docker启动指令 CPU docker run --rm -it -d -p 8380:8080 -p 8381:8081 --name torch-server -v /path/model-server/extra-files:/home/model-serve…...
mybatis开启日志
步骤很详细,直接上教程 配置文件的文件格式可能有所不同,这里列举两种 配置方法 一. application.properties(默认 # 配置mybatis的日志信息 mybatis.configuration.log-implorg.apache.ibatis.logging.stdout.StdOutImpl二. application.y…...
MobaXterm : Network error: Connection refused(连接被拒绝)
具体报错如下如所示: 首先进行问题排查 ① 检查SSH服务是否运行 sudo service ssh status ② 检查SSH服务是否已启动(启用返回 enable) sudo systemctl is-enabled ssh ③ 查看所有的端口 sudo netstat -tulnp ④ 查看SSH使用的22号端口有…...
电脑的主板,内存条插多少合适?
首先,不是插满4条内存就是最好的。 内存条插得多,确实可以扩充容量,提升性能。但是有些低端的主板配低端CPU,插满4条内存,稳定性下降。这里的稳定性包括供电,单独的内存供电容量等。此时CPU会通过降低内存…...
C++:初始化列表
构造函数在上一篇帖子我们提到了对成员变量初始化的功能,出了在构造函数的函数体中队成员变量一个一个赋值以外,我们还可以采用初始化列表。 #include<iostream> using namespace std;class AA { private:int a;const int b; public:AA():b(200),…...
[000-01-008].第05节:OpenFeign特性-重试机制
我的后端学习大纲 SpringCloud学习大纲 1.1.重试机制的默认值: 1.重试机制默认是关闭的,给了默认值 1.2.测试重试机制的默认值: 1.3.开启Retryer功能: 1.修改配置文件YML的配置: 2.新增配置类: packa…...
【SpringBoot】100、SpringBoot中使用自定义注解+AOP实现参数自动解密
在实际项目中,用户注册、登录、修改密码等操作,都涉及到参数传输安全问题。所以我们需要在前端对账户、密码等敏感信息加密传输,在后端接收到数据后能自动解密。 1、引入依赖 <dependency><groupId>org.springframework.boot</groupId><artifactId...
DAY 47
三、通道注意力 3.1 通道注意力的定义 # 新增:通道注意力模块(SE模块) class ChannelAttention(nn.Module):"""通道注意力模块(Squeeze-and-Excitation)"""def __init__(self, in_channels, reduction_rat…...
《通信之道——从微积分到 5G》读书总结
第1章 绪 论 1.1 这是一本什么样的书 通信技术,说到底就是数学。 那些最基础、最本质的部分。 1.2 什么是通信 通信 发送方 接收方 承载信息的信号 解调出其中承载的信息 信息在发送方那里被加工成信号(调制) 把信息从信号中抽取出来&am…...
python报错No module named ‘tensorflow.keras‘
是由于不同版本的tensorflow下的keras所在的路径不同,结合所安装的tensorflow的目录结构修改from语句即可。 原语句: from tensorflow.keras.layers import Conv1D, MaxPooling1D, LSTM, Dense 修改后: from tensorflow.python.keras.lay…...
MySQL的pymysql操作
本章是MySQL的最后一章,MySQL到此完结,下一站Hadoop!!! 这章很简单,完整代码在最后,详细讲解之前python课程里面也有,感兴趣的可以往前找一下 一、查询操作 我们需要打开pycharm …...
comfyui 工作流中 图生视频 如何增加视频的长度到5秒
comfyUI 工作流怎么可以生成更长的视频。除了硬件显存要求之外还有别的方法吗? 在ComfyUI中实现图生视频并延长到5秒,需要结合多个扩展和技巧。以下是完整解决方案: 核心工作流配置(24fps下5秒120帧) #mermaid-svg-yP…...
深入解析光敏传感技术:嵌入式仿真平台如何重塑电子工程教学
一、光敏传感技术的物理本质与系统级实现挑战 光敏电阻作为经典的光电传感器件,其工作原理根植于半导体材料的光电导效应。当入射光子能量超过材料带隙宽度时,价带电子受激发跃迁至导带,形成电子-空穴对,导致材料电导率显著提升。…...
使用python进行图像处理—图像滤波(5)
图像滤波是图像处理中最基本和最重要的操作之一。它的目的是在空间域上修改图像的像素值,以达到平滑(去噪)、锐化、边缘检测等效果。滤波通常通过卷积操作实现。 5.1卷积(Convolution)原理 卷积是滤波的核心。它是一种数学运算,…...
C/Python/Go示例 | Socket Programing与RPC
Socket Programming介绍 Computer networking这个领域围绕着两台电脑或者同一台电脑内的不同进程之间的数据传输和信息交流,会涉及到许多有意思的话题,诸如怎么确保对方能收到信息,怎么应对数据丢失、被污染或者顺序混乱,怎么提高…...
解决MybatisPlus使用Druid1.2.11连接池查询PG数据库报Merge sql error的一种办法
目录 前言 一、问题重现 1、环境说明 2、重现步骤 3、错误信息 二、关于LATERAL 1、Lateral作用场景 2、在四至场景中使用 三、问题解决之道 1、源码追踪 2、关闭sql合并 3、改写处理SQL 四、总结 前言 在博客:【写在创作纪念日】基于SpringBoot和PostG…...
