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

这篇具有很好参考价值的文章主要介绍了蓝桥杯一维差分 | 算法基础。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

简单说两句

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

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

CSDN个人主页:后端小知识

🔎GZH后端小知识

🎉欢迎关注🔎点赞👍收藏⭐️留言📝文章来源地址https://www.toymoban.com/news/detail-775674.html

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

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

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

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

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

概念

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

在算法和计算机科学中,差分(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上面的模板题:

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

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

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

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

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

相关文章

  • 算法基础之差分和前缀和

    结论:差分是前缀和的逆运算 举例 一维差分 二维差分 用在一维子区间里的数都增减一个固定值,把对于区间内每个数的操作转换为对于差分数组中的端点的操作,时间复杂度降为o(1)。 用在二维子矩阵里的数都增减一个固定值,把对于子矩阵的每个数的操作转换为对应差分

    2024年02月07日
    浏览(43)
  • 【算法基础】前缀和与差分

    😽 PREFACE 🎁欢迎各位→点赞 👍 + 收藏 ⭐ + 评论 📝 📢系列专栏: 算法 💪 种一棵树最好是十年前其次是现在 前缀和指一个数组的某下标之前的所有数组元素的和(包含其自身)。前缀和分为一维前缀和,以及二维前缀和。前缀和是一种重要的预处理,能够降低算法的时

    2024年01月19日
    浏览(32)
  • 【算法基础2】前缀和与差分

    前缀和是某数列的前n项数的和,而差分则可以看做是前缀和的逆运算。前缀和与差分比起是一种算法,更像是一种解决问题的思路,通过构造一个特殊的数组,就可以让我们将某些复杂的问题简化。 (1)一维前缀和 已知一个数列a[n],用S[n]来表示这个数列的前n项和数列。

    2024年04月14日
    浏览(40)
  • 用Matlab求解一维非稳态导热问题(有限差分法+显式离散)

    章熙民的第六版《传热学》里,较为简单的介绍了非稳态导热的数值计算,本文根据此书,以计算一个可视为无限大平壁的复合墙体传热过程为例,讨论一维非稳态导热问题数值求解的问题。 这里把参考书目的PDF分享出来,希望可以帮助到大家学习传热学,里面有章熙民的第

    2023年04月22日
    浏览(42)
  • 【OI学习笔记】基础算法-前缀和与差分算法

    板块:基础算法、线性优化 难度:较易 前置知识:C++基础语法 在一维空间中,对于一个数据总量为 n n n 的数组 a a a ,有数据 a [ 1 ] , a [ 2 ] , a [ 3 ] , . . . , a [ n − 1 ] , a [ n ] a[1],a[2],a[3],...,a[n-1],a[n] a [ 1 ] , a [ 2 ] , a [ 3 ] , ... , a [ n − 1 ] , a [ n ] ,定义一个数组 s u m sum s u m ,

    2024年02月08日
    浏览(48)
  • C++基础算法前缀和和差分篇

    📟作者主页:慢热的陕西人 🌴专栏链接:C++算法 📣欢迎各位大佬👍点赞🔥关注🚓收藏,🍉留言 主要讲解了前缀和和差分算法 Ⅵ .Ⅰ前缀和 ① 一维前缀和 : ​ 就是构建一个新的数组 s ,用来存储另一个数组的和前 i 个数组元素的和。用公式表达就是: S [ i ] = a [ 0 ]

    2024年02月16日
    浏览(48)
  • 【有营养的算法笔记】基础算法 —— 推导证明前缀和与差分

    👑作者主页:@安 度 因 🏠学习社区:StackFrame 📖专栏链接:有营养的算法笔记 如果无聊的话,就来逛逛 我的博客栈 吧! 🌹 Hello,小伙伴们,好几天没有更新了,今天更了一篇比较“硬核的文章”。 主要内容为前缀和与差分算法的推导证明和代码实现。这篇文章博主还是画

    2024年01月21日
    浏览(46)
  • 算法基础学习笔记——④前缀和\差分\双指针\位运算

    ✨ 博主: 命运之光 ✨ 专栏: 算法基础学习 目录 ✨前缀和 ✨一维前缀和 🍓一维前缀和模板: ✨二维前缀和 🍓二位前缀和模板: 前言: 算法学习笔记记录日常分享,需要的看哈O(∩_∩)O,感谢大家的支持! 原i:a[1] a[2] a[3] …a[n] 前缀和:s[i]=a[1]+a[2]+…+a[i] s[0]=0(方便处理

    2024年02月08日
    浏览(46)
  • [蓝桥杯Python]算法练习、算法基础、算法训练、算法模板(持续更新)

    [蓝桥杯Python]算法练习、算法基础、算法训练、算法模板( 持续更新..... ) 目录 一、算法基础 1.Huffuman树 2.Sine之舞 3.数列排序 4.数列排序 5.特殊回文数 6.回文数 7.特殊的数字 8.杨辉三角形 9.高精度加法 10.Fibonacci数列 11.报时助手 12.回形取数 13.矩阵乘法 二、算法提高 1.印章

    2023年04月08日
    浏览(46)
  • 蓝桥杯-双指针 | 最长连续不重复子序列 | 算法基础

    ⭐ 简单说两句 ⭐ ✨ 正在努力的小新~ 💖 超级爱分享,分享各种有趣干货! 👩‍💻 提供:模拟面试 | 简历诊断 | 独家简历模板 🌈 感谢关注,关注了你就是我的超级粉丝啦! 🔒 以下内容仅对你可见~ 作者: 后端小知识 , CSDN后端领域新星创作者 |阿里云专家博主 CSDN 个

    2024年02月03日
    浏览(45)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包