一维差分
输入一个长度为 n 的整数序列。接下来输入 m个操作，每个操作包含三个整数 l,r,c，表示将序列中 [l,r] 之间的每个数加上 c ，请你输出进行完所有操作后的序列。
输入格式
第一行包含两个整数 n 和 m
第二行包含 n 个整数，表示整数序列。
接下来 m行，每行包含三个整数 l，r，c，表示一个操作。
输出格式
共一行，包含 n 个整数，表示最终序列。
数据范围
1≤n,m≤100000 , 1≤l≤r≤n , −1000≤c≤1000 , −1000≤整数序列中元素的值≤1000
输入样例：
6 3 1 2 2 1 2 1 1 3 1 3 5 1 1 6 1
输出样例：
3 4 5 3 4 2
本题大概题意是求出一个数组的差分数组，假定原数组为a[],
所求差分数组 b[],公式为 b[i]=a[i]-a[i-1] ,可知：
差分数组b[]的前缀和数组，就是原数组a[],也就是说，
差分 和 前缀和互为逆运算
差分数组的作用
差分数组能快速的对给定范围内的数组统一的增加或者减少大小，
要让原数组a[]在[i,j]的范围内的数值都加上一个value，那么只需要在差分数组b[]上进行改动：
b[i]+=c b[j+1]-=c
根据原数组是差分数组的前缀和这一原理很好理解
解题思路：
我们可以假定原数组元素全为0，
那么差分数组也全为0，
那么我们可以遍历一遍差分数组，然后对其进行插入操作
for(int i=1;i<=n;i++) insert(i,i,a[i]);//insert函数里面改变的是b数组的值
1.现在所求的b[]数组便是一个差分数组，
当然也可以用**b[i]=a[i]-a[i-1]**来求差分数组
2.然后就是在差分数组内进行插入修改
3.最后对整个差分数组进行一次前缀和
4.输出数组即可
代码：
#include<iostream> using namespace std; const int N=100010; int a[N]; int b[N]; void insert(int l,int r,int val) { b[l]+=val; b[r+1]-=val; } int main() { int n,m; 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]); 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]; for(int i=1;i<=n;i++) printf("%d ",b[i]); return 0;
差分矩阵
输入一个 n行 m列的整数矩阵，再输入 q 个操作，每个操作包含五个整数 x1,y1,x2,y2,c，其中 (x1,y1)和 (x2,y2) 表示一个子矩阵的左上角坐标和右下角坐标。
每个操作都要将选中的子矩阵中的每个元素的值加上 c。
请你将进行完所有操作后的矩阵输出。
输入格式
第一行包含整数 n,m,q
接下来 n 行，每行包含 m个整数，表示整数矩阵。
接下来 q 行，每行包含 5个整数 x1,y1,x2,y2,c，表示一个操作。
输出格式
共 n 行，每行 m 个整数，表示所有操作进行完毕后的最终矩阵。
数据范围
1≤n,m≤1000 , 1≤q≤100000 , 1≤x1≤x2≤n , 1≤y1≤y2≤m , −1000≤c≤1000 ,
−1000≤矩阵内元素的值≤1000
输入样例：
3 4 3 1 2 2 1 3 2 2 1 1 1 1 1 1 1 2 2 1 1 3 2 3 2 3 1 3 4 1
输出样例：
2 3 4 1 4 3 4 1 2 2 2 2
本题就是求一个二维差分矩阵，大致思路和上题一致，在求差分时需要画图理解一下
红颜色部分是我们需要改变数组的区域
先根据公式 b[i][j]=b[i-1][j]+b[i][j-1]-b[i-1][j-1]+b[i][j];
在画图可知
就可以理解公式了，
题解：
先求出差分数组
在根据题目要求对差分数组进行插入操作
然后求出差分数组的前缀和数组
最后数组该数组即可
代码：
#include<iostream> using namespace std; const int N=1010; int a[N][N]; int b[N][N]; void insert(int x1,int y1,int x2,int y2,int val) { b[x1][y1]+=val; b[x1][y2+1]-=val; b[x2+1][y1]-=val; b[x2+1][y2+1]+=val; } int main() { int n,m,q; cin>>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; cin>>x1>>y1>>x2>>y2>>c; insert(x1,y1,x2,y2,c); } for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { b[i][j]=b[i-1][j]+b[i][j-1]-b[i-1][j-1]+b[i][j]; } } for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { cout<<b[i][j]<<' '; } cout<<endl; } return 0; }
结语
如果觉得有帮助的话，记得
一键三连哦ヾ(≧▽≦*)o。
