⭐简单说两句⭐
✨ 正在努力的小新~
💖 超级爱分享,分享各种有趣干货!
👩💻 提供:模拟面试 | 简历诊断 | 独家简历模板
🌈 感谢关注,关注了你就是我的超级粉丝啦!
🔒 以下内容仅对你可见~作者:后端小知识,CSDN后端领域新星创作者 |阿里云专家博主
CSDN个人主页:后端小知识
🔎GZH:
后端小知识
文章来源:https://www.toymoban.com/news/detail-775674.html🎉欢迎关注🔎点赞👍收藏⭐️留言📝文章来源地址https://www.toymoban.com/news/detail-775674.html
亲爱的友友们,我们今天来学习一个简单而又常用的算法(比赛中遇到了就赚大发了额😎)
这个算法的名字就叫做 差分算法
差分算法在各种算法比赛中使用到的频率还是不低的,大家一定要掌握哟,主要是这个算法也比较简单,容易理解
我们本次讲解只讲解一维差分,二维差分我们后续再讲,只要你把一维差分理解到位了,二维差分也是直接拿下🌈
概念
我们先来了解一下一些概念性的东西
在算法和计算机科学中,差分(Differential)通常指的是一种数据结构,它用于高效地存储和查询序列中元素的增量。这种数据结构特别适用于那些元素之间存在固定增量的序列
差分数组
差分数组是一种优化的数据结构,它通过存储序列的增量来减少计算时间。给定一个序列 A
,其差分数组 D
可以通过以下方式构建:
- 初始化一个空数组
D
。 - 对于序列
A
中的每个元素A[i]
(从i = 1
到n
,其中n
是序列的长度),计算D[i] = A[i] - A[i-1]
(如果i
是序列的第一个元素,则D[i] = A[i]
)。 - 最终,差分数组
D
的第一个元素D[0]
通常被设置为0
(或者序列的第一个元素,取决于具体应用)。
是不是感觉特别简单啊,那我们来实践一下,加深理解😍
例子
我们来看一道Acwing上面的模板题:
🔗我也直接给家人们要来了(贴心吧❤️):差分
这个题目的意思是不是特别简单啊,我们最直观的做法就是写个双重循环直接干,但是看这数据范围肯定会TLE的💣
我们必须得优化,怎么优化呢,就要用到我们上面说的差分了,
思路
我们定义一个差分数组b,b[i] = a[i]-a[i-1] (i>=1),
📢:b[0]=a[0]
我们简单列举几项
b[1]=a[1]-a[0]
b[2]=a[2]-a[1]
b[3]=a[3]-a[2]
…
b[i]=a[i]-a[i-1]
好啦🌶,我们要求a[i]的话,是不是就是求b[i]+b[i-1]+…b[0]啊
所以a[i]=b[i]+b[i-1]+…b[0]
这些理清楚后,我们来看下怎么做增加操作
我们要在a数组的 l 到 r 区间 给每个数加上c , 如果我们直接去操作a数组,需要操作r-l次
注意啦,我们不去操作a数组,我们去动b数组
我们将 b[l] + c ,这样就相当于a[l] 后面的所有数都加上了c
然后 b[r+1]-c,这里为什么 要 减去c呢? 就是因为刚刚把l后面的都加上了c,而从r+1开始,我们又不要+c,所以得减去c
👩🏻💻答疑环节
有的小伙伴可能有疑问了为什么b[l]+c 就相当于a[l] 后面的所有数都加上了c
我们假设一下,我们求 a[l+3]的值
根据公式来
a[l+3]=b[l+3]+b[l+2]+b[l+1]+b[l]+b[l-1]+…b[0]
因为我们刚刚对b[l]加了c,所以a[l+3] 肯定是比之前的值大c的
怎么样,理解了吗?如果还有不理解的地方可以再评论区留言或者厚台滴滴我哟🤓
OK,理论都整清楚了,我们接下来写写code吧
代码
AC 代码清单
#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[100010];
int b[100010];
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i],b[i]=a[i]-a[i-1];
while(m--){
int l,r,c; cin>>l>>r>>c;
b[l]+=c;b[r+1]-=c;
}
int sum=0;
for(int i=1;i<=n;i++){
sum+=b[i];
cout<<sum<<" ";
}
return 0;
}
看了代码后是否加深了理解了呢,如果大家还有任何疑问的话欢迎大家来和我交流哟😎
【都看到这了,点点赞点点关注呗,爱你们】😚😚
💬
✨ 正在努力的小新~
💖 超级爱分享,分享各种有趣干货!
👩💻 提供:模拟面试 | 简历诊断 | 独家简历模板
🌈 感谢关注,关注了你就是我的超级粉丝啦!
🔒 以下内容仅对你可见~
作者:后端小知识,CSDN后端领域新星创作者 | 阿里云专家博主
CSDN个人主页:后端小知识
🔎GZH:后端小知识
🎉欢迎关注🔎点赞👍收藏⭐️留言📝
到了这里,关于蓝桥杯一维差分 | 算法基础的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!