前言

天梯赛和省赛快开始了，不想拖后腿，边更边学习吧。

酝酿好久的第一篇博客，缺点不少，多多指教吖。

点赞鼓励一下吧，亲。😙😙

正文

一、算法原理

差分和前缀和算法的核心或可浓缩成以下等式：

a[i]=s[i]-s[i-1]

它是利用差分数组和前缀和数组的对应关系，改变其中之一，而影响另一的算法。差分与前缀是两个相反的过程,其中差分旨在以递推的形式记录数组元素,前缀和是以求和的方式灵活地面对区间询问。前缀和可以理解为数学中数列的前n项和，而差分则是其逆过程。

前缀和数组：用以存储已知数组的前n项和，设为s，其中s[i]存放已知数组的前i项和。

差分数组：用以存储已知前缀和数组的各个项，设为a，其前i项和为已知数组的第i项。

因此，差分与前缀和的关键是构造前缀和数组或差分数组。

二、算法图解

差分与前缀和是针对数组的算法，而数组又分为一维与多维，因此差分与前缀和也包括一维与多维两种(因二维最为常见，故本篇只讨论二维)，不过二者原理相同，形变神不变。

一维前缀和

watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETkDkuqbmnKjkuI1lbW8,size_20,color_FFFFFF,t_70,g_se,x_16

不难看出，一维的前缀和可理解为前n项和，因此得到一维前缀和的预处理公式： · a[i]=s[i]-s[i-1]

二维前缀和

watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETkDkuqbmnKjkuI1lbW8,size_20,color_FFFFFF,t_70,g_se,x_16

从图中我们很容易看出，整个外围蓝色矩形面积s[i][j] = 绿色面积s[i-1][j] + 紫色面积s[i][j-1] - 重复加的红色的面积s[i-1][j-1]+小方块的面积a[i][j];

因此得出二维前缀和预处理公式

s[i] [j] = s[i-1][j] + s[i][j-1 ] + a[i] [j] - s[i-1][ j-1]

一维差分

watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETkDkuqbmnKjkuI1lbW8,size_20,color_FFFFFF,t_70,g_se,x_16

让[L，R]区间的每个元素都加一，可以构造差分数组b[]。作b[l] + c，效果使得a数组中 a[l]及以后的数都加上了c(红色部分)，但我们只要求l到r区间加上c, 因此还需要执行 b[r+1] - c,让a数组中a[r+1]及往后的区间再减去c(绿色部分)，这样对于a[r] 以后区间的数相当于没有发生改变。

因此我们得出一维差分结论：给a数组中的[ l, r]区间中的每一个数都加上c,只需对差分数组b做 b[l] + = c, b[r+1] - = c。时间复杂度为O(1), 大大提高了效率。

二维差分

用数组c存储总改变量。在c[x1][y1]处加上a，在c[x2+1][y1]和c[x1][y2+1]处减a，在c[x2+1][y2+1]再加上a。最后(i,k)位置上的数值就是c数组在(i,k)位置的前缀和。c即为构造的差分数组。

三、算法模板

一维前缀和

#include<bits/stdc++.h>
using namespace std;
int main () 
{   int a[100001],sum[100001];int i,j,k,p,n,q;cin>>n>>q;for(i=1;i<=n;i++)cin>>a[i];for(i=1;i<=n;i++)      //求前缀和数组 sum[i]=sum[i-1]+a[i];while(q--)             //进行q次询问并输出 { cin>>k>>p;cout<<sum[p]-sum[k-1]<<"\n";	}	
}

二维前缀和

#include<bits/stdc++.h>
using namespace std;
int main()
{  int a[100][100],s[100][100],i,j,k,x1,y1,x2,y2,n;cin>>n>>m;for(i=1;i<=n;i++)  for(j=1;j<=m;j++){ cin>>a[i][j];s[i][j]=a[i][j]+s[i-1][j]+s[i][j-1]-s[i-1][j-1];} cin>>x1>>y1>>x2>>y2;cout<<s[x2][y2]-s[x2][y1-1]-s[x1-1][y2]+a[x1-1][y1-1];}

一维差分

#include<bits/stdc++.h>
using namespace std;
int main () 
{   int a[100001],b[100001];int i,l,r,c,p,n,q;cin>>n>>q;for(i=1;i<=n;i++)   //求差分数组 { cin>>a[i];b[i]=a[i]-a[i-1];} while(q--)         //进行q次询问 { cin>>l>>r>>c;b[l]=b[l]+c;b[r+1]=b[r+1]-c;}for(i=1;i<=n;i++)  //输出改变后的数组 { b[i]=b[i]+b[i-1];cout<<b[i]<<" ";}
}

二维差分

#include<bits/stdc++.h>
using namespace std;
int main()
{  int n,m,a[100][100],s[100][100],i,j,x1,y1,x2,y2;cin>>m>>n;for(i=1;i<=m;i++) for(j=1;j<=n;j++) cin>>s[i][j];cin>>x1>>y1>>x2>>y2;a[x1][y1]++;a[x2+1][y2+1]--;for(i=1;i<=m;i++) for(j=1;j<=n;j++) a[i][j]=s[i][j]-s[i][j-1]-s[i-1][j]+s[i-1][j-1];for(i=1;i<=m;i++) for(j=1;j<=n;j++) if(j==n) cout<<s[i][j]<<"\n";else cout<<s[i][j]<<" ";
}