[基础算法](4)前缀和与差分
引言
前缀和与差分是一堆逆运算，前缀和用来求一段区间的和，设前缀和数组为 s 原数组为 a
，则s是a的前缀和数组，a为s的差分数组
若想详细了解该算法，可移步大佬博客，这儿只做复习记录用:林深不见鹿 的博客-CSDN博客_前缀和与差分
一维前缀和
模板题:795. 前缀和 - AcWing题库
一维前缀和思路很简单，扫一遍累加起来就好了
代码：
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define NUM_MAX 100010
int nums[NUM_MAX];
int main(){
int n,m,l,r;
scanf("%d %d",&n,&m);
memset(nums,0,sizeof(nums));
for(int i=1;i<=n;i++){
scanf("%d",&nums[i]);
nums[i]+=nums[i-1];
}
while(m--){
scanf("%d %d",&l,&r);
printf("%d\n",nums[r]-nums[l-1]);
}
return 0;
}二维前缀和
模板题:796. 子矩阵的和 - AcWing题库
核心思路:
紫色面积是指(1,1)左上角到(i,j-1)右下角的矩形面积, 绿色面积是指(1,1)左上角到(i-1, j )右下角的矩形面积。每一个颜色的矩形面积都代表了它所包围元素的和。
因此二维前缀和的结论为：
以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵的和为：
s[x2, y2] - s[x1 - 1, y2] - s[x2, y1 - 1] + s[x1 - 1, y1 - 1]不理解的看视频:
代码：
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAX 1010
int Matrix[MAX][MAX];
int main(){
for(int i=0;i<MAX;i++)
memset(Matrix[i],0,sizeof(Matrix[MAX]));
int m,n,q;
scanf("%d %d %d",&n,&m,&q);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
scanf("%d",&Matrix[i][j]);
Matrix[i][j]=Matrix[i-1][j]+Matrix[i][j-1]-Matrix[i-1][j-1]+Matrix[i][j];
}
}
int x1,x2,y1,y2;
while(q--){
scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
printf("%d\n",Matrix[x2][y2]-Matrix[x1-1][y2]-Matrix[x2][y1-1]+Matrix[x1-1][y1-1]);
}
return 0;
}一维差分
引言:
差分的作用在于 区间更新 ，可以想象 若要在一段区间内同时加上一个数，则需要O(n)的世界复杂度去将其每一个元素都加上这个数
然而将其转换为差分数组 则只需要在左端点加上这个数，右端点再减去这个数，O(1)的时间复杂度即可完成
模板题:797. 差分 - AcWing题库
代码：
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAX 100010
int nums[MAX];
int b[MAX];
//单点更新
void updata(int l,int r,int c){
b[l]+=c;
b[r+1]-=c;
return;
}
int main(){
int n,m;
memset(b,0,sizeof(b));
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",&nums[i]);
b[i]=nums[i]-nums[i-1];//构造差分序列
}
int l,r,c;
while(m--){
scanf("%d %d %d",&l,&r,&c);
updata(l,r,c);
}
for(int i=1;i<=n;i++){
b[i]+=b[i-1];//恢复原序列
printf("%d ",b[i]);
}
return 0;
}二维差分
模板题:798. 差分矩阵 - AcWing题库
这题只需要清楚了每个点的包含范围即可。
代码：
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAX 1010
int Matrix[MAX][MAX];//原矩阵
int b[MAX][MAX];//差分矩阵
void updata(int x1,int y1,int x2,int y2,int c){//单点更新
b[x1][y1]+=c;//左上角总范围整体加上c
b[x1][y2+1]-=c;//右上角次范围整体减去c
b[x2+1][y1]-=c;//左下角次范围整体减去c
b[x2+1][y2+1]+=c;//多减去的部分加上c
return;
}
int main(){
int n,m,q;
for(int i=0;i<MAX;i++)
memset(b[i],0,sizeof(b[i]));
scanf("%d %d %d",&n,&m,&q);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
scanf("%d",&Matrix[i][j]);
b[i][j]=Matrix[i][j]-Matrix[i-1][j]-Matrix[i][j-1]+Matrix[i-1][j-1];
}
}
int x1,y1,x2,y2,c;
while(q--){
scanf("%d %d %d %d %d",&x1,&y1,&x2,&y2,&c);
updata(x1,y1,x2,y2,c);
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
b[i][j]=b[i][j]+b[i-1][j]+b[i][j-1]-b[i-1][j-1];
printf("%d ",b[i][j]);
}
printf("\n");
}
return 0;
}