零基础学算法100天第7天——二维差分（差分矩阵）

本文已收录于专栏 🌲《零基础学算法一百天》🌲

学习指引

• 1、什么是差分矩阵？
• 2、差分矩阵的核心操作
• 3、预处理得到差分数组
• 4、差分矩阵模板题

⭐️引言⭐️

  大家好啊，我是执梗。今天零基础学算法要讲解的是前缀和与差分系列的终章——二维差分。这算是这个里面相对复杂一点的知识点，但也仅仅是一点，只要掌握好了前缀和+一维差分，通过图解理解起来还是非常快的。虽然考的很少，但是也是一门必须掌握地基础算法。

1、什么是差分矩阵？

  二维差分我们通常称之为差分矩阵。通过结合一维差分我们可以想到，它的作用是可以让某个子矩阵在O(1)的时间复杂度内让所有元素都加上c。

  而我之前一直都在强调一点——前缀和与差分是逆运用，二维亦是如此。

  如果我们有了一个b[][]如图：

​   很明显它的二维前缀和数组a[][]应该为：

  两者的关系为——$a是b的前缀和数组，而b是a的差分数组（差分矩阵）$

2、差分矩阵的核心操作

  我们前面已经提过，差分矩阵b[][]是帮助我们在O(1)时间内让原数组a[][]的某个子矩阵加上c。类似二维前缀和的讲解，通过图解能最快速帮忙大家理解差分矩阵的核心操作 :

  1、首先我们有一个如图的数组a[][] ，我们想让红色板块的值都加上c

  

  2、如果我们此时对数组b[][]的该点加上c

  

  3、因为a[][]是b[][]的前缀和数组，根据二维前缀和的初始化出发，会使得a[][]以下子矩阵全部都加上c

  

  4、很显然，增加的面积超出了我们想要的范围，所以我们还需要减去a[][]中这两个子矩阵的面积

  

​   

  5、又可以很明显的发现，减去的这两个子矩阵有重合的地方，我们多减了一次，最后还需要加回来，对于这两个减去子矩阵以及加回多减的操作。我们只需要让b[][]的绿色两点减上c，红色点加上c
  

   总结：我们假设在第一步中a[][]需要增加的子矩阵的左上角坐标为(x1,y1),右下角坐标为(x2,y2)。根据刚才的分析，对于a[][]任意子矩阵的增加c的操作，我们只需要对b[][]进行两增两减的操作即可，这样的时间复杂度稳定是O(1)的。

   我们来对比一下朴素与差距矩阵的优化操作：

   朴素版实现O(n*n)：

for(int i=x1;i<x2;++i){for(int j=y1;i<=y2;++j{a[i][i]+=c;}}

   差分矩阵核心操作O(1)

//差分矩阵最核心的操作   static void insert(int x1,int y1,int x2,int y2,int c){       s[x1][y1]+=c;       s[x1][y2+1]-=c;       s[x2+1][y1]-=c;       s[x2+1][y2+1]+=c;   }

3、预处理得到差分数组

  这时候肯定有人有疑问，你光说了差分矩阵多牛了，那问题是我们有的数组是a[][]，那怎么通过a[][]得到它的差分矩阵b[][]呢？这就是二维差分一个比较难理解的点，我们讲二维前缀和的时候是先讲的如何先预处理得到二维前缀和数组，再讲如何使用，而差分矩阵恰好应该反过来。
  因为从差分矩阵的定义我们很难直接得到，一维的差分数组从定义出发来说，我们可以很轻松的通过b[i]=a[i]-a[i-1]得到差分数组。但差分矩阵你就会觉得很别扭，怎么感觉那么奇怪呢？💢
b[i][j]==???，很难想到。
  但是我们可以曲线救国 ❗️

 我们先假设a[][]为空全为0，那么此时它的差分矩阵b[][]理所当然也是全为0的，这时对于a[][]中任意一个坐标(i,j)，我们把它既当做左上角坐标，也当做右下角坐标，对其进行insert操作（也就是上面说的最核心操作）。因为一个格子也可以看作是一个子矩阵，这样对于a[][]的每个格子我们都进行insert操作，最终就可以得到我们的差分矩阵b[][]。

   预处理操作：

//差分数组的预处理(曲线救国)       for(int i=1;i<=n;++i)           for (int j=1;j<=m;++j){               a[i][j]=sc.nextInt();               insert(i,j,i,j,a[i][j]);           }

4、差分矩阵模板题

   根据前面的讲解，直接进行操作即可，先预处理得到差分矩阵b[][]，再进行m次insert操作，最后通过二维前缀和推导由b[][]推回我们的原数组a[][]即可。

import java.util.Scanner;public class Main {   static int N=1010;   static int[][] a=new int[N][N];   static int[][] s=new int[N][N];   static int n,m,q;   public static void main(String[] args) {       Scanner sc=new Scanner(System.in);       n=sc.nextInt();       m=sc.nextInt();       q=sc.nextInt();       //差分数组的预处理(曲线救国)       for(int i=1;i<=n;++i)           for (int j=1;j<=m;++j){               a[i][j]=sc.nextInt();               insert(i,j,i,j,a[i][j]);           }       while (q-->0){           int x1=sc.nextInt();           int y1=sc.nextInt();           int x2=sc.nextInt();           int y2=sc.nextInt();           int c=sc.nextInt();           insert(x1,y1,x2,y2,c);       }          //求回原数组a，其实就是求二维前缀和的过程(前面的文章讲过)       for (int i = 1; i <=n; i++) {           for (int j = 1; j <=m; j++) {               a[i][j]=a[i-1][j]+a[i][j-1]-a[i-1][j-1]+s[i][j];               System.out.print(a[i][j]+" ");           }              System.out.println();       }   }   //差分矩阵最核心的操作   static void insert(int x1,int y1,int x2,int y2,int c){       s[x1][y1]+=c;       s[x1][y2+1]-=c;       s[x2+1][y1]-=c;       s[x2+1][y2+1]+=c;   }}

如果文章对你有所帮助，还望能给点三连支持一下，非常感谢！！！

来源地址：https://blog.csdn.net/m0_57487901/article/details/124859474