前缀和
前缀和概念
前缀和指的是用另一个数组b[n]来保存a[n]中前n项的和
例如，b[0]=a[0],b[1]=a[0]+a[1],…
应用
求数组某一区间长度数字的和
如果我给你一串长度为n的数列a1,a2,a3……an,再给出m个询问，每次询问给出L，R两个数，要求给出区间[L,R]里的数的和，一般可能是从L到R遍历一次，但这样很花时间，有了前缀和之后可以直接b[R]-b[L]就得到L到R的和
差分
差分就是将数列中的每一项分别与前一项数做差
一个序列1 2 5 4 7 3，差分后得到1 1 3 -1 3 -4 -3
这里注意得到的差分序列第一个数和原来的第一个数一样（相当于第一个数减0）
差分序列最后比原序列多一个数（相当于0减最后一个数）
例 给你一串长度为n的数列a1,a2,a3……an，要求对a[L]~a[R]进行m次操作：
操作一：将a[L]~a[R]内的元素都加上P
操作二：将a[L]~a[R]内的元素都减去P
最后再给出一个询问求a[L]-a[R]内的元素之和？
如果用一般做法就是遍历加减，时间复杂度高，现在可以直接让b[L] 加上P，再让b[R+1]减去P，这样因为b[L+1]=b[L]+a[L+1]，所以L到R上每一项都会加P，而b[R+1]减去P是为了对后面的数不产生影响
如果有多次修改操作，可以先将每次修改保存到一个数组中，然后求前缀和时再加上
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+9;
int a[maxn],b[maxn];
int main(){
int i,j,k,n,m,p;
cin>>n>>m;
for(i=1;i<=n;i++){
cin>>a[i];
}
for(i=1;i<=m;i++){
int L,R,t;
cin>>t>>L>>R>>p;
if(t==1){
b[L]+=p;b[R+1]-=p; //仔细想想为什么b[R+1]要减去p
}
else{
b[L]-=p;b[R+1]+=p;//这是减去p
}
}
int add=0;
for(i=1;i<=n;i++){
add+=b[i];
a[i]+=a[i-1]+add;//这是求前缀和数组，并且add是把需要加p的地方加上
}
int x,y;
cin>>x>>y;
cout<<a[y]-a[x-1]<<endl;
}
性质：
1、差分序列求前缀和可得原序列
2、将原序列区间[L,R]中的元素全部+1，可以转化操作为差分序列L处+1，R+1处-1
3、按照性质2得到，每次修改原序列一个区间+1，那么每次差分序列修改处增加的和减少的相同
二维前缀和
二维前缀和对应的是二维数组
b[2][4]表示的是b[1][1]+b[1][2]+b[1][3]+b[1][4]+b[2][1]+b[2][2]+b[2][3]
因此可以先加上b[1][4]+b[2][3]，这时重复了b[1][3]，再减去
因此公式
a[i][j]+=a[i][j-1]+a[i-1][j]-a[i-1][j-1]，因为这样，二维前缀和最好从一开始，0处全赋值为0
这时想知道从(x1,y1)到(x2,y2)的和要a[x2][y2]-a[x1-1][y2]-a[x2][y1-1]+a[x1-1][y1-1]
例如，求(3,3)到(4,4)的值，实际上是a[3][3]+a[3][4]+a[4][3]+a[4][4]
二维差分（不是很清楚）
和一维差分的第四个问题类似，让（x1,y1)和（x2,y2）矩形内的数都加上x
b[x1][y1]+=x; b[x2+1][y2+1]+=x;
b[x1][y2+1]-=x; b[x2+1][y1]-=x;
参考博客https://blog.csdn.net/k_r_forever/article/details/81775899