前缀和与差分:
前缀和:即指某个序列的前n项和 差分:即前缀和的逆过程

1.一维前缀和与二维前缀和:
一维前缀和:(1).预处理(O(n)),s[i]统计a[1]--a[i]的和
(2).查询(O(1)):要查从l--r的值的和即等于s[r]-s[l-1]
即:S[i]=a[1]+a[2]+...+a[i] a[l]+a[l+1]+...+a[r]=s[r]-s[l-1]

二维前缀和:(1).预处理复杂度O(n*m) (2).查询:O(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]

一维前缀和的应用:
对一长度为n的序列,每次询问给定一个l和r,求其从l到r的元素和
分析:对于本题如果采用传统的方式,每次询问就从l到r进行一次求和,则时间的复杂度为O(n*m),如果使
用前缀和的知识,就可以先进行一遍预处理O(n),接下来的m次询问的时间复杂度为O(1)*m,所以总的时间复
杂度为O(n+m)
代码如下: 

求前缀和的运算

int sum[maxn],a[maxn];
for (int i=1;i<=n;i++) 
	sum[i]=sum[i-1]+a[i];

查询操作:

int l,r,ans;
scanf("%d%d",&l,&r);
ans=sum[r]-sum[l-1];//注意此处不是sum[r]-sum[l]! 

二维前缀和的应用:
输入一个n行m列的矩阵,多次询问给定两个点的坐标(x1,y1),(x2,y2),表示一个子矩阵的左上角和右下角
求这个子矩阵的所有元素的和
代码如下: 
求前缀和(预处理):

int a[maxn][maxn],s[maxn][maxn];
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]+a[i][j]-s[i-1][j-1];

每次询问处理:

int x1,y1,x2,y2,ans;
while (q--) {
	scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
	ans=s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1];
	printf("%d",ans);
} 

2.一维差分与二维差分
一维差分:(1).差分数组:给定一个原数组a[1],a[2],...,a[n];在构造一个新的数组b[1],b[2],...,b[n]
使得a[i]=b[1]+b[2]+...+b[i],所以已知a[i]求b[i]的过程就是一个差分的过程,而已知b[i]求a[i]的过
程则是前缀和的过程,所以差分是前缀和的逆运算
差分的方法:a[0]=0,b[1]=a[1]-a[0],b[2]=a[2]-a[1]...,b[n]=a[n]-a[n-1]

一维差分的应用:1.若对m次询问l,r,要使a[l]--a[r]的所有数都加上c,如果每次都按照操作从l-r去加上
某一个数,那么时间的复杂度为O(n*m),但使用一个差分数组b[i]后,我们只需要将b[l]+c,那么l以后的所
有a[i]都会加上c,所以我们只需要在将r以后的数减掉一个c即可,即将b[r+1]-c,所以操作的时间复杂度被
降为O(n+2*m),时间复杂度大幅度降低
代码实现: 

 求差分的运算:

int a[maxn],b[maxn]; 
for (int i=1;i<=n;i++) {
    scanf("%d",&a[i]);
    b[i]=a[i]-a[i-1];
}  

询问处理操作:

while (q--) {
    scanf("%d%d%d",&l,&r,&c);
    b[l]+=c;
    b[r+1]-=c;
} 

二维差分:二维差分不好直接构造差分数组,我们可用差分数组的特点去构造一些数,然后得到需要的差
分数组,所以如果要使以(x1,y1)为左上角的点,(x2,y2)为右下角的点的矩阵全部加c,仅需对假定构造好
的差分数组b进行以下操作即可: 

void insert(int x1,int x2,int y1,int y2,int c) {
    b[x1][y1]+=c;
    b[x1+1][y2]-=c;
    b[x2][y1+1]-=c;
    b[x2+1][y2+1]+=c;
} 

在构造一个二重循环每次都执行一遍insert就可以构造出所需要的差分数组

for (int i=1;i<=n;i++) {
    for (int j=1;j<=m;j++) {
        insert(i,j,i,j,a[i][j]);
    }
} 

当然二维差分数组也可以直接进行构造(其与二维前缀和数组的构造基本类似):

b[i][j]=a[i][j]-a[i-1][j]-a[i][j-1]+a[i-1][j-1]; 

前缀和与差分