2025年【学习算法】差分

大家好，我是讯享网，很高兴认识大家。

一、基本思想

【一维差分】

【二维差分】

二、代码模板

三、经典例题

【例一】差分

题目描述：

代码：

【例二】差分矩阵

题目描述：

代码：

一、基本思想

【一维差分】

1、什么是差分？

差分是前缀和的逆运算；

给定数组a：a[1]，a[2]，a[3]，…… a[n]

构造数组b：b[1]，b[2]，b[3]，…… b[n]

使得 a[i] = b[1]+b[2]+……+b[i];(即数组a是数组b的前缀和)

b称为a的差分，a称为b的前缀和。

可知：

讯享网

b[1]=a[1];

b[2]=a[2]-a[1];

……

b[n]=a[n]-a[n-1]

2、差分的作用及原理

作用：将数组 a 区间[l，r]中的所有数都 + c，暴力做法需要遍历一遍，时间复杂度为O(n)，但差分可以实现用 O(1)的时间给原数组a中间的某一段连续区间全部加上一个固定的值。

原理：

①数组b[l] + c ~ a[l] + c (因为a[l]==b[1]+b[2]+……+b[l]) ~ a[l]……a[n] 全部 + c;

②由于我们只需要将区间 [l，r] 中的数 + c，所以 b[r+1] - c（b[r+1] - c ~ a[r+1] - c，即 a[r+1] ……a[n]全部 - c，与步骤①中区间 [r+1，n] + c相互抵消）; 实现只改变数组a在区间 [l，r]上的值想法。

综上所述，我们只需要改变 b[l] 和 b[r+1] 这两个数的值，时间复杂度为O(1)。

注：“~”表示“相当于”，“-”表示“减”，“c”表示“常数”。

3、差分的实现

假定数组a初始时全部为0，那么差分数组b也全部为0；

可以将数组a看成是在初始条件下进行了n次插入操作，即a[1]~原数组区间[1，1] + a[1]…… a[n]~原数组区间 [n，n] + a[n] ,不需要进行数组b 的构造，实现起来比较方便。

【二维差分】

二、代码模板

//一维差分 给区间[l, r]中的每个数加上c：B[l] += c, B[r + 1] -= c

讯享网

讯享网//二维差分 给以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵中的所有元素加上c： S[x1, y1] += c, S[x2 + 1, y1] -= c, S[x1, y2 + 1] -= c, S[x2 + 1, y2 + 1] += c

三、经典例题

【例一】差分

题目描述：

代码：

#include<bits/stdc++.h> using namespace std; const int N=; int n,m; int a[N],b[N];//分别表示原数组和差分数组 int insert(int l,int r,int c) { b[l]+=c; b[r+1]-=c; } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=1;i<=n;i++) insert(i,i,a[i]); //将原数组的n个数插入,相当于构造差分数组b while(m--) { int l,r,c; scanf("%d%d%d",&l,&r,&c); insert(l,r,c); } //求一下原来数组的值 for(int i=1;i<=n;i++) { b[i]+=b[i-1]; //将b数组变成自己的前缀和 } for(int i=1;i<=n;i++) printf("%d ",b[i]); return 0; }

【例二】差分矩阵

题目描述：

代码：

讯享网#include<bits/stdc++.h> using namespace std; const int N=1010; int n,m,q; int a[N][N],b[N][N]; void insert(int x1,int y1,int x2,int y2,int c) { b[x1][y1] += c; b[x2+1][y1] -= c; b[x1][y2+1] -= c; b[x2+1][y2+1] += c; } int main() { scanf("%d%d%d",&n,&m,&q); //输入 for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&a[i][j]); for(int i=1;i<=n;i++) //插入 for(int j=1;j<=m;j++) insert(i,j,i,j,a[i][j]); while(q--) //依次操作 { int x1,y1,x2,y2,c; scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&c); insert(x1,y1,x2,y2,c); } for(int i=1;i<=n;i++) //将前缀和存入b for(int j=1;j<=m;j++) b[i][j] += b[i-1][j]+b[i][j-1]-b[i-1][j-1]; for(int i=1;i<=n;i++) //输出 { for(int j=1;j<=m;j++) printf("%d ",b[i][j]); printf("\n"); } return 0; }

2025年【学习算法】差分

一、基本思想

【一维差分】

【二维差分】

二、代码模板

三、经典例题

【例一】差分

题目描述：

代码：

【例二】差分矩阵

题目描述：

代码：

相关推荐