蓝桥杯一维差分 | 算法基础

2024-01-01 20:43:49

?简单说两句?

? 正在努力的小新~
💖 超级爱分享,分享各种有趣干货!
👩?💻 提供:模拟面试 | 简历诊断 | 独家简历模板
🌈 感谢关注,关注了你就是我的超级粉丝啦!
🔒 以下内容仅对你可见~

作者:后端小知识CSDN后端领域新星创作者 |阿里云专家博主

CSDN个人主页后端小知识

🔎GZH后端小知识

🎉欢迎关注🔎点赞👍收藏??留言📝

image-20231222230153568

亲爱的友友们,我们今天来学习一个简单而又常用的算法(比赛中遇到了就赚大发了额😎)

这个算法的名字就叫做 差分算法

差分算法在各种算法比赛中使用到的频率还是不低的,大家一定要掌握哟,主要是这个算法也比较简单,容易理解

我们本次讲解只讲解一维差分,二维差分我们后续再讲,只要你把一维差分理解到位了,二维差分也是直接拿下🌈

概念

我们先来了解一下一些概念性的东西

在算法和计算机科学中,差分(Differential)通常指的是一种数据结构,它用于高效地存储和查询序列中元素的增量。这种数据结构特别适用于那些元素之间存在固定增量的序列

差分数组

差分数组是一种优化的数据结构,它通过存储序列的增量来减少计算时间。给定一个序列 A,其差分数组 D 可以通过以下方式构建:

  1. 初始化一个空数组 D
  2. 对于序列 A 中的每个元素 A[i](从 i = 1n,其中 n 是序列的长度),计算 D[i] = A[i] - A[i-1](如果 i 是序列的第一个元素,则 D[i] = A[i])。
  3. 最终,差分数组 D 的第一个元素 D[0] 通常被设置为 0(或者序列的第一个元素,取决于具体应用)。

是不是感觉特别简单啊,那我们来实践一下,加深理解😍

例子

我们来看一道Acwing上面的模板题:

🔗我也直接给家人们要来了(贴心吧??):差分

image-20231222222602766

这个题目的意思是不是特别简单啊,我们最直观的做法就是写个双重循环直接干,但是看这数据范围肯定会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后端小知识

🎉欢迎关注🔎点赞👍收藏??留言📝

文章来源:https://blog.csdn.net/m0_46833224/article/details/135328277
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。