前言

差分与前缀和是为解决一下矩阵部分和的问题与求矩阵问题（关系）a1.....an---->(构造)b1----bn，a是b的前缀和，b是a的差分

转换方法

一维前缀和

S[i] = a[1] + a[2] + … a[i]
a[l] + … + a[r] = S[r] - S[l - 1]

二维前缀和

S[i, j] = 第i行j列格子左上部分所有元素的和以(x1, y1)为左上角，(x2,y2)为右下角的子矩阵的和为 S[x2, y2] - S[x1 - 1, y2] - S[x2, y1 - 1] + S[x1- 1, y1 - 1]

一维差分

B[i] = a[i] -a[i-1]给区间[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

相关题解

一维前缀和

 [原题链接](https://www.acwing.com/problem/content/797/) 

 #include< iostream >
using namespace std;
const int N=1e5+10;
int n,m;
int a[N],s[N];
int main(){
    cin>>n>>m;
    //坐标从一开始，避免避免边界问题
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++)s[i]=s[i-1]+a[i];//初始化
    while(m--){
        int l,r;
        cin>>l>>r;
        cout<<s[r]-s[l-1]<<endl;
    }
    return 0;
}



###   二维前缀和


[原题链接](https://www.acwing.com/problem/content/798/) 

#include< iostream >
using namespace std;
const int N=1010;
int a[N][N],s[N][N];
int n,m,q;

int main(){
    cin>>n>>m>>q;
    for(int i=1;i<=n;i++)
     for(int j=1;j<=m;j++)
           cin>>a[i][j];
      for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        //初始化
              s[i][j]=a[i][j]+s[i-1][j]+s[i][j-1]-s[i-1][j-1];
   while(q--)
   {
       int x1,y1,x2,y2;
       cin>>x1>>y1>>x2>>y2;
       //左上角与左下角的差
       cout<<s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1]<<endl;

   }
   return 0;
}