前缀和，差分
前缀和问题描述
前缀和：什么是前缀和，顾名思义前面数字的和嘛，对于一组数据，a1,a2,a3,a4,……an 1到4的前缀和就是a1+a2+a3+a4. 3到7的前缀和就是a3+a4+a5+a6+a7. 前缀和解释完毕。如果用s集合表示前缀和，下标i表示1到i的前缀和，那么s[i]=s[i-1]+a[i]. 二维前缀和： s[i][j]表示第i行，第j列的前缀和，第i行和第j列包含的左上角的加起来的和就是前缀和，如图：红色的部分就是前缀和了。
那么，s[i][j]该怎么求呢？思考一下，在去求s[i][j]的时候，前面的i-1，j-1，i-2等等是不是都求过了。 我们把a[i][j]拿出来，
s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j],读者朋友可以把图像化一下就能很好理解了。
前缀和
这道题是求两个区间（l,r）的之间的和，不就是s[r]-s[l-1]的值嘛。ok问题解决，代码开始，主要先求出前缀和。
cpp#include <iostream>
using namespace std;
int main()
{
int n,q;
cin>>n>>q;
int* a=new int[n+1]{0};
long long* s=new long long[n+1]{0};
for(int i=1;i<=n;i++)
{
cin>>a[i];
s[i]=s[i-1]+a[i];
}
while(q--)
{
int l,r;
cin>>l>>r;
cout<<s[r]-s[l-1]<<endl;
}
return 0;
}二维前缀和
该问题也是求得某一个位置的前缀和，比如：求的是(x1,y1)和(x2,y2)之间的前缀和。 下面的公司不懂的读者画一下图 那么该结果==s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1]. 上代码：
cpp#include <iostream>
#include <vector>
using namespace std;
int main()
{
int n,m,q;
cin>>n>>m>>q;
vector<vector<int>> a(n+1,vector<int>(m+1)) ;
vector<vector<long long>> s(n+1,vector<long long>(m+1));
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>a[i][j];
s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];
}
}
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;
}差分问题描述
什么是差分？对于一组数据a1,a2,a3,a4……an——前缀和数据 那么差分数据就是构成前缀和的。假设差分数据为b1,b2,b3,b4……bn 它们俩满足ai=b1+b2……+bi 即： a1=b1 a2=b2-b1 …… 二维差分：对于一组二维数据，b[1][1],b[1][2]……b[n][n]——差分数据 a[i][j]数据就是b数据以i行j列的前缀和。
差分
该题是要在[l,r]区间加上一个常数，如果之间相加的化，时间复杂度O(N^2),如果用差分的化就可以把时间复杂度降到O(N). 怎么搞呢？ 对于一组数据a1,a2,a3,a4........an,要在[l,r]上加上一个常数k，我们只需要在b[l]处加上k（b[l]+=k）这会使从l往后的位置的前缀和就加上了一个常数k，只要我们在r往后的地方删去k——b[r+1]-=k,根据它们满足的关系ai=b1+b2……+bi，我们就可以完成在[l,r]的区间内加上常数k. 我们要做的是先获取差分
cpp#include <iostream>
#include <vector>
using namespace std;
void f(int l,int r,int k,vector<long long>& b)
{
//a是前缀和数组
b[l]+=k;//b[l]=a[l]-a[l-1];
b[r+1]-=k;//b[r+1]=a[r+1]-a[r];
//a[t]'=b[0]+ +b[t]=a[t]+k; r<=t<=l
//b[r]-=k;的作用是让后面的前缀和+k，
//b[r+1]-=k;的作用是让后面的前缀和-k
//中和一下，只有区间内不得前缀和也就是原数组的值统一加上了k。
}
int main()
{
int n,m;
cin>>n>>m;
vector<long long> a(n+1),b(n+1);
for(int i=1;i<=n;i++)//输入数据，并且获得差分
{
cin>>a[i];
f(i,i,a[i],b);
//思考一下为啥可以这样，该含义表示什么
//——在i到i的范围内前缀和加上a[i],
//而我们的b[1]到b[i]的和就是a[i],刚好满足。仔细想，认真思考这里
//构造差分数组，差分数组初始化全为0;真神奇啊！
}
//通过修改差分数组b为原数组a（l,r）区间的元素都加上k.
//时间复杂度O(1);
while(m--)
{
int l,r,k;
cin>>l>>r>>k;
f(l,r,k,b);
}
//求前缀和
for(int i=1;i<=n;i++)
{
a[i]=a[i-1]+b[i];
cout<<a[i]<<' ';
}
cout<<endl;
return 0;
}二维差分
要在某个平面内，加上一个常数k，比如：在（x1,y1），(x2,y2)的区域内加上k 我们可以像一维差分那样，那么公式为：b[x2+1][y2+1]+=k,b[x1][y2+1]-=k,b[x2+1][y1]-=k,b[x1][y1]+=k;即可满足上述需求，具体可以看下面的图
cpp#include <iostream>
#include <vector>
using namespace std;
void f(int x1,int y1,int x2,int y2,long long k,vector<vector<long long>>&b)
{
//思想和一维
b[x2+1][y2+1]+=k;
b[x1][y2+1]-=k;
b[x2+1][y1]-=k;
b[x1][y1]+=k;
}
int main()
{
int n,m,q;
cin>>n>>m>>q;
vector<vector<long long>> a(n+2,vector<long long>(m+2)),b(n+2,vector<long long>(m+2));
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>a[i][j];
f(i,j,i,j,a[i][j],b);
}
}
while(q--)
{
int x1,y1,x2,y2,k;
cin>>x1>>y1>>x2>>y2>>k;
f(x1,y1,x2,y2,k,b);
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
a[i][j]=a[i][j-1]+a[i-1][j]-a[i-1][j-1]+b[i][j];
cout<<a[i][j]<<' ';
}
cout<<endl;
}
return 0;
}腾讯云开发者
