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

蔚落 2024-04-20 07:37 58阅读 0赞

⭐**简单说两句**⭐

> **✨ 正在努力的小新~**  
> **? 超级爱分享，分享各种有趣干货！**  
> **?? 提供：模拟面试 | 简历诊断 | 独家简历模板**  
> **? 感谢关注，关注了你就是我的超级粉丝啦！**  
> **? 以下内容仅对你可见~**
> 
> **作者：****后端小知识**，**CSDN后端领域新星创作者 |阿里云专家博主**
> 
> **CSDN**个人主页：[后端小知识][Link 1]
> 
> ?**GZH**：`后端小知识`
> 
> ?欢迎关注?点赞?收藏⭐️留言?

![image-20231222230153568][]

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

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

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

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

### 概念 ###

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

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

**差分数组**

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

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

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

### 例子 ###

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

?我也直接给家人们要来了（贴心吧❤️）：[差分][Link 2]

![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;
    }

看了代码后是否加深了理解了呢，如果大家还有任何疑问的话欢迎大家来和我交流哟?

【都看到这了，点点赞点点关注呗，爱你们】??

![抽象工厂  引导关注][199c21e10d589f1889bfb9e864daecc6.png]

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

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

**CSDN**个人主页：[后端小知识][Link 1]

?**GZH**：`后端小知识`

?欢迎关注?点赞?收藏⭐️留言?

[Link 1]: https://blog.csdn.net/m0_46833224
[image-20231222230153568]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/f6b2c87bcad54d2caf855869afe76ee6.png
[Link 2]: https://www.acwing.com/problem/content/description/799/
[image-20231222222602766]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/3f8ecbe96c34453ab042c89b789698a6.png
[199c21e10d589f1889bfb9e864daecc6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/ae8df20aafd4429485e9e854553ea65d.png