4.前缀和与差分
1.一维前缀和
一维前缀和：S[i]=a1+a2+a3+a4+…+ai，要求a从a1开始，且S[0]=0
前缀和的作用：给定一组序列数据，可以计算任意第l个数到第r个数的和，S[r]-S[l-1]（这里就解释了为什么要求S[0]=0，因为当l=1时，实质就是求是S[r]）
求很多个任意子序列的数据和时，假如不使用前缀和公式，就需要顺序遍历来求，时间复杂度为O(n)
使用前缀和，直接得到结果，时间复杂度为O(1)
AcWing 795.前缀和
#include <iostream>
using namespace std;
const int N=1e6+10;
int n,m;
int a[N],s[N];
int main(){
cin>>n>>m;
//注意数组下标从1开始存储
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=n;i++) S[i]=S[i-1]+a[i];//因为S[]为全局数组，元素默认初始化为0
while(m--){
int l,r;
cin>>l>>r;
cout<<S[r]-S[l-1]<<endl;
}
return 0;
}
2.二维前缀和
二维前缀和：S[i][j]即为坐标(i,j)左上部分所有元素的和，也就是绿色区域的所有元素和（注意i，j依旧是从1开始，s[0][0]默认为0）
二维前缀和计算公式：s[i][j]=s[i][j-1]+s[i-1][j]-s[i-1][j-1]+a[i][j]（注意这里要s[i][j-1]+s[i-1][j]多算了一次s[i-1][j-1]，所以要减去一次）
任意子矩阵中所有数的和计算：
设所求子矩阵的左上角坐标为(x1,y1)，右下角坐标为(x2,y2)
s=s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1]
eg:s=S[5][3] - S[2][3] - S[5][1] + S[2][1]
AcWing 796.子矩阵的和
#include <iostream>
using namespace std;
int n,m,q;
int N=1e6+10;
int a[N][N],s[N][N];
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]=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[x2][y1-1]-s[x1-1][y2]+s[x1-1][y1-1]<<endl;
}
return 0;
}
3.一维差分
差分实质是前缀的逆运算
假设有一个数组，a{1}，a{2}，a{3}，a{4}，a{5}，…，a{n}
针对这个数组，构造出另一个数组，b{1}，b{2}，b{3}，b{4}，b{5}，…，b{n}
使得a数组是b数组的前缀和，即使得 a{i} = b{1} + b{2} + … + b{i}；b{i}=a{i}-a{i-1}
差分的作用：
若要对a数组中[l, r]区间内的全部元素都加上一个常数C，若直接操作a数组的话，需要循环遍历，时间复杂度是O(n)。而如果操作其差分数组b，则时间复杂度是O(1)。即可以用O(1)的时间给某一数组的某一子序列元素都加上一个值
具体实现：
数组a是数组b的前缀和数组，只要对 b{l}这个元素加C，则a数组从l位置之后的全部数都会被加上C，但r位置之后的所有数也都加了C，所以我们通过对 b{r+1} 这个数减去C，来保持a数组中r位置以后的数的值不变，即a数组r位置以后的数都是+C-C抵消。
于是，对a数组的[l, r]区间内的所有数都加上一个常数C，就可以转变为对
b{l}+C，对b{r+1}-C。对于构造差分数组b：
在输入数组a时，可以先假想数组a和数组b的全部元素都是0。然后每次进行一次插入操作（指的是对数组a的[l, r]区间的每个数加上常数C），比如对a数组区间[1,1]，加（插入）常数a{1}，效果就是
b{1}=b{1}+a{1}，b{2}=b{2}-a{1}；对区间[2,2]，加常数a{2}，效果就是b{2}=b{2}+a{2}，b{3}=b{3}-a{2},…，这样在输入数组a的同时，就能够快速构造出其差分数组b。实际就把构造数组b的过程看作为给一个数组中[l, r]区间内的全部元素都加上一个常数C的过程，只不过特殊的是这个数组元素都为0，这个区间为[i,i]，这个常数C会变化为a[i]
AcWing 797.差分
#include <iostream>
using namespace std;
int n,m;
int N=1e6+10;
int a[N],b[N];
void insert(int l,int r,int c){
b[l]+=c;
b[r+1]-=c;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>a[i];
for(int i=1;i<=n;i++)
insert(i,i,a[i]);//构造差分数组b
while(m--){
int l,r,c;
cin>>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++) cout<<b[i]<<" ";
return 0;
}
4.二维差分
类比一维差分和二维前缀和，二维差分的作用：以时间复杂度O(1)对任意子矩阵加上一个常数
具体实现：
期望对矩阵a中左上角为[x1, y1]，右下角为[x2, y2]的区域内的全部元素，都加一个常数C，则可以转化为对其差分矩阵b的操作。
先对b中[x1, y1]位置上的元素加C，这样以来，前缀和a中[x1, y1]这个点的右下角区域内的所有数都加上了C，但是这样就对[x2, y2]之后的区域也都加了C。
我们对[x2, y2]之外的区域需要保持值不变，所以需要进行减法。对b{x2+1,y1} 减掉C，这样下图红色区域都被减了C，再对b{x1,y2+1}减掉C，这样下图蓝色区域都被减了C，而红色区域和蓝色区域有重叠，重叠的区域被减了2次C，所以要再加回一个C，即对b{x2+1,y2+1}加上一个C。这样，就完成了对[x1, y1]，[x2, y2]区域内的所有数（下图绿色区域），都加上常数C。
构造差分二维数组b
思想和一维差分一样，假设二维数组a和二维数组b初始化都为0，在输入
a[i][j]时就可顺便构造b[i][j]。实际就把构造数组b的过程看作为给一个数组中[x1, y1]，[x2, y2]区域内的全部元素都加上一个常数C的过程，只不过特殊的是这个数组元素初始都为0，这个区域为[i,j]到[i,j]（即就是一个元素），这个常数C会变化为a[i][j]
AcWing 798.差分矩阵
#include <iostream>
using namespace std;
int n,m,q;
int N=1e6+10;
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(){
cin>>n>>m>>q;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>a[i][j];
//构造差分数组b[][]
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)
}
//求差分数组b[][]的前缀和 即加完常数的数组a
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
b[i][j]=b[i-1][j]+[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;
}