零基础学算法100天第6天——差分(基础算法)

简介: 前两天的零基础算法系列我们讲了一维与二维的前缀和,既然讲了前缀和那就不得不讲它的兄弟——差分。差分的本质,实际上就是前缀和的逆运用,掌握好了前缀和那么差分也就是砍瓜切菜。差分也是一个非常重要的知识点,大家一定要掌握好!

🔥 1.什么是差分数组?


差分数组本质上和前缀和数组就是相对的。


我们直接通过两个数组来对比即可知道。


image.png


显而易见,数组b是数组a的前缀和数组。而相对而言,我们称数组a是数组b的差分数组。


🍋2.差分数组的预处理  


       差分数组的预处理还是非常简单的,从前缀和预处理逆过来推理即可。由我们之前学过前缀和的定义可以知道:对于任意一个数组b中的元素:


image.png


       所以这个公式就是我们差分数组预处理的核心步骤,如果有原数组b[],通过这样处理即可得到我们的差分数组a[]。


for(int i=1;i<=n;i++){
     b[i]=a[i]-a[i-1];
  }


🍅3.差分数组的使用


       既然我们知道了如何得到差分数组,那到底差分数组有什么用呢?这个我们同样通过分析数组a和数组b之间的关系。


       由于b是a的前缀和数组,所以前面我们有这样一个式子:


      image.png


       如果我们对某个ai加上一个常数d对b数组有什么影响?


    从上面的式子可以看出来,如果ai加上了d,bi的值会加上d,那么会影响bi-1吗?肯定是没有影响的,因为bi-1的值是从a1加到ai-1。那么对bi之后的的数有影响吗?是有的,因为


bi+1是从a1加到ai+1,这其中包括了ai,所以bi+1的值也会加上d,后面的数同理。    


       从这样分析我们可以看出,当我们对差分数组某个数ai进行操作时,会将原数组[bi,bn]所有数都产生影响。这样可以让我们优化很多操作。


1、让原数组区间[L,R]都加上d        


       对于这个操作,按照朴素的做法,我们需要对原数组从L到R循环遍历过去加上d。这样的时间复杂度是O(R-L),当区间足够长时,时间复杂度会达到O(n),需要遍历整个数组。但如果我们原数组的差分数组进行操作时,只需要对L和R位置进行操作即可,对L位置加上d,就会使得原数组从L开始全部数加上d,对R+1位置减去d,就会使得原数组从R+1开始所有的数减去d,综合起来就能让原数组[L,R]区间都加上d。这样无论L到R的范围有多大,我们只需要对两个位置进行操作,时间复杂度稳定到O(1)。


      核心操作:


public static void insert(int l,int r,int c,int[] b){
        b[l]+=c;
        b[r+1]-=c;
    }


🌸4.模板题解析



image.png


        由于对原数组操作复杂度过高,我们先得到差分数组,然后对差分数组进行操作,最后操作完毕后再对原数组进行复原即可,复原的操作就是获得前缀和数组。


       代码转换:


import java.util.Scanner;
import java.io.*;
class Main{
    static BufferedWriter log = new BufferedWriter(new OutputStreamWriter(System.out));
    public static void main(String[] args)throws Exception{
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int m=sc.nextInt();
        //原数组
        int[] a=new int[n+1];
        //差分数组,开n+2的长度,防止在insert中b[r+1]时数组越界
        int[] b=new int[n+2];
        for(int i=1;i<n+1;++i){
            a[i]=sc.nextInt();
        }
        //获取差分数组
        for(int i=1;i<n+1;i++){
            b[i]=a[i]-a[i-1];
        }
        while(m-->0){
            int l=sc.nextInt();
            int r=sc.nextInt();
            int c=sc.nextInt();
            insert(l,r,c,b);
        }
        //读回原数组a
        for(int i=1;i<n+1;i++){
            a[i]=a[i-1]+b[i];
            log.write(a[i]+" ");
            log.flush();
        }
    }
    //核心操作
    public static void insert(int l,int r,int c,int[] b){
        b[l]+=c;
        b[r+1]-=c;
    }
}


相关文章
|
存储 算法 数据管理
【C/C++ 基础算法】 C/C++ 位图算法的使用
【C/C++ 基础算法】 C/C++ 位图算法的使用
285 0
|
10天前
|
机器学习/深度学习 传感器 算法
【高创新】基于优化的自适应差分导纳算法的改进最大功率点跟踪研究(Matlab代码实现)
【高创新】基于优化的自适应差分导纳算法的改进最大功率点跟踪研究(Matlab代码实现)
97 14
|
15天前
|
机器学习/深度学习 边缘计算 分布式计算
基于差分进化算法的微电网调度研究(Matlab代码实现)
基于差分进化算法的微电网调度研究(Matlab代码实现)
|
4月前
|
机器学习/深度学习 算法
基于差分进化灰狼混合优化的SVM(DE-GWO-SVM)数据预测算法matlab仿真
本项目实现基于差分进化灰狼混合优化的SVM(DE-GWO-SVM)数据预测算法的MATLAB仿真,对比SVM和GWO-SVM性能。算法结合差分进化(DE)与灰狼优化(GWO),优化SVM参数以提升复杂高维数据预测能力。核心流程包括DE生成新种群、GWO更新位置,迭代直至满足终止条件,选出最优参数组合。适用于分类、回归等任务,显著提高模型效率与准确性,运行环境为MATLAB 2022A。
|
7月前
|
机器学习/深度学习 算法 机器人
强化学习:时间差分(TD)(SARSA算法和Q-Learning算法)(看不懂算我输专栏)——手把手教你入门强化学习(六)
本文介绍了时间差分法(TD)中的两种经典算法:SARSA和Q-Learning。二者均为无模型强化学习方法,通过与环境交互估算动作价值函数。SARSA是On-Policy算法,采用ε-greedy策略进行动作选择和评估;而Q-Learning为Off-Policy算法,评估时选取下一状态中估值最大的动作。相比动态规划和蒙特卡洛方法,TD算法结合了自举更新与样本更新的优势,实现边行动边学习。文章通过生动的例子解释了两者的差异,并提供了伪代码帮助理解。
434 2
|
人工智能 算法 JavaScript
【算法】前缀和与差分
算法学习——前缀和与差分(含一维和二维)
156 4
【算法】前缀和与差分
|
12月前
|
人工智能 算法 BI
一篇带你速通差分算法(C/C++)
一篇带你速通差分算法(C/C++)
|
算法 C++
c++算法学习笔记 (5)前缀和+差分
c++算法学习笔记 (5)前缀和+差分
|
人工智能 移动开发 算法
算法基础:前缀和与差分
算法基础:前缀和与差分
135 1
算法基础:前缀和与差分
|
存储 机器学习/深度学习 人工智能
【算法基础】基础算法(三)--(双指针算法、位运算、离散化、区间合并)
【算法基础】基础算法(三)--(双指针算法、位运算、离散化、区间合并)

热门文章

最新文章