对前缀和与差分进行总结，来源：洛谷题单
首先
（由于之前教练和我说可以刷一刷洛谷的题单刷刷基础我就去了
正文
前缀和有几种，一维和二维的用的比较多。
一维前缀和比较简单，直接将数组的前几个加起来成一个单独的数组就可以
二维前缀和有点不一样：我们的二维前缀和处理的过程中不能直接通过上一个得到（需要三步操作其实也相当于直接得到。。。
在进行循环的时候，我们可以设想一下：
1 2 3
1 2 3
1 2 3
的前缀和 f[2][3]等于什么
显然它可以从 f[2][2]和 f[1][3]转移过来
但是都不一样 f[2][2]+f[1][3]会把 f[1][2]算两次
所以……减一下就可以
方程：f[i][j]=f[i-1][j]+f[i][j-1]-f[i-1][j-1];
就可以进行处理了
二维前缀和的例题：洛谷 P2004 领地选择
题目链接
一道模板题。。。
处理二维前缀和，四个角顶点 x1,x2,y1,y2(x1<x2,y1<x2)ans=max(ans,f[x2][y2]-f[x1][y2]-f[x2][y1]+f[x1][y1]);
怎么推导意会一下就可以很简单
差分
差分是一种很妙的算法，有的时候他可以自己单独成题，有的时候也可以配合着前缀和
因为：前缀和与差分是一对逆操作，前缀和序列差分一下就是原序列，差分序列前缀和一下也是原序列
例题 1 IncDec Sequence CH0304（简称：蓝书例题）
给定一个长度为 n(1e5)的序列，每次可以选择一个区间+1 或者-1
求至少多少次可以让序列所有数相等，再求，最少次数之下，序列最后多少种可能的值
序列所有数都相等代表了：差分序列除了第一个之外都为 0
那么：我们让差分序列 b 的 bn+1=0，每一次进行区间加减的时候都代表着我们要对差分序列中的两个数一个+1 另一个-1；
我们的目的是让 b2~bn 变成 0.
由于加一减一都是可以的，那么我们就没有区间进行加减时是否需要考虑+1 在前还是-1 在前这个限制了
（之前考试的时候有一道题是只给减法的，就比这个难一点，但其实也就相当于是特判，不难）
我们可以进行分类讨论： 1.选 bi,bj，在一个正另一个负的时候多进行操作 2.选 b1,bj，1 选完之后考虑 3.选 bi,bn+1，同样是 1 选完之后考虑
4.b1,bn+1，没有意义，舍去（因为 b1,bn+1 并不会对序列造成影响
第 1 类操作我们可以直接进行判断，判断序列中正数负数的绝对值，这两个的差就是 1 的次数
而第二第三次直接判断剩下的就可以，因为 2，3 操作事实上等价
综上所述，这个题第一问的答案就是两个数绝对值最大的那个（正负数分别的和的 max）
而第二问：因为是要求最小次数，操作一的次数等无影响，反正都会消耗完
那就考虑第 2,3 次操作的次数
如果我们第 2,3 次操作次数为 m
我们就可以进行选择进行那次操作，每次选择操作会不一样，但既然是问值，那就询问差分序列的第一个值
考虑操作 2，每一次的操作 2 都会对 b1 进行更改，操作 2 至少 0 次，最多 m 次，共 m+1 中可能
m=max(p,q)-min(p,q)
完美解决。。。
例题 2 洛谷 P2671 求和
前缀和好题
题目链接
我们先考虑题中给的三元组（x,y,z）
y-x=z-y 那么说明，x,z 同奇或者同偶
既然如此，我们考虑对 color 下手：
每一个 color 的奇数偶数分别存储，他们中的每一个都可以单独构成一个三元组
三元组的分数：
编号之和乘数字之和
如果一个一个找，复杂度会炸
那么我们就可以看看这个分数能不能下手：显然可以
(x+z)(numx+numz)=xnumx+znumx+numzx+znumz
在每一个三元组，我们的 xnumx 都会被算到，那就统计一下三元组的个数，运用结合律把这么多的三元组进行结合律
我们数列中的元素回合所有其他的元素构成一个三元组从而被算一次（不管比他小还是比他大）
元素还会和其他元素的 num 都乘一次
那么我们处理 cnt 数组（就是记录 color 奇数偶数的那个）乘奇偶数的前缀和减去当前的数加上 cnt 数组乘当前的数字
这道题就被巨佬的您切掉了
总结
总之前缀和与差分是可以用到很多的地方的
插粉还可以用在你自己想要的区间求和
比如你想让一段序列都加都减，直接在差分序列上改一改最后求一个前缀和就可以了
很 nice