前缀和 差分问题

一维前缀和
sum[i]=sum[i-1]+a[i];
一维差分的引入:
给你一串长度为n的数列a1,a2,a3…an，要求对a[L]~a[R]进行m次操作：

操作一：将a[L]~a[R]内的元素都加上c

操作二：将a[L]~a[R]内的元素都减去c

最后再给出一个询问求a[L]-a[R]内的元素之和？

你会怎么做呢？你可能会想，我对于m次操作每次都遍历一遍a[L]~a[R],给区间里的数都加上c或减去c，最后再求一次前缀和就行了。没错，这样子确实也能得出正确答案，但时间复杂度却高达O(M*n)，对于1<=n,m<=1e5这个数据范围来说直接就GG了，所以说这个方法不可行

解决：
我们要在一个区间[l,r]内都加上一个数a，那么像树状数组去区间更新一样，我们弄一个差分数组,在dif[l]处+a，在dif[r+1]处-a,这样像前缀和一样扫过l到r这个区间时，在l处开始有+a，+a对[l,r]区间产生影响，在r+1处-a变回原来的值，对r+1后面的区间没有了影响

二维前缀和

当要求红色部分，(0,0)到（i,j）处的前缀和时，我们黄色部分和蓝色部分已经是已知的了，而它们重叠的部分就是绿色部分，所以把黄色和蓝色部分的结果加起来，再减去绿色部分，最后加上(i,j)处的值就是（i，j）位置的前缀和了。

sum[i][j]几何意义是从{0,0}到{i,j}的前缀和是多少?
所以，二维前缀和就是sum[i][j]=a[i][j]+sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]

新的问题又来了
如果我们给出左上角坐标和右下角坐标 求一段区间和怎么解决呢？

我们要求紫色部分的值，我们已知的是黄色部分的值，但它多了两个蓝色部分的值，而两个蓝色部分有重叠了个绿色部分

所以要求的区间内的值就是sum[x2][y2]-sum[x2][y1-1]-sum[x1-1][y2]+sum[x1-1][x1-1]

二维差分

这里是重点

在我们要的区间开始位置（x1,y1）处+a，根据前缀和的性质，那么它影响的就是整个黄色部分，多影响了两个蓝色部分，所以在两个蓝色部分-a消除+a的影响，而两个蓝色部分重叠的绿色部分多受了个-a的影响，所以绿色部分+a消除影响。

所以就是dif[x1][y1]+=a,dif[x1][y2+1]-=a,dif[x2+1][y1]-=a,dif[x2+1][y2+1]+=a