[基础算法](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;
}

本文链接：