写这篇博客是因为前一天遇到了二维前缀和的题目，趁着这次机会（还没忘）赶紧梳理一下前缀和以及区分一下和它很像的差分
一、从一维讲起的前缀和
前缀和——一听就知道是与总和密切相关的变量，那么究竟是什么原理呢？
对于一个数列（如1，3，5，7，9），我们在求其某一位或某几位数的总和时，一般采用累加的方式，而前缀和就是记录到每一位位置之前所以数累加的和。
这样其实会有一次复杂度为O(n)的遍历，和一般直接求和复杂度基本一致，为什么还要多此一举呢？原因在于我们一般将前缀和与动态规划及其它需要频繁调用数据的算法相结合，这些情况下前缀和只用遍历一次，复杂度远远低于一般求和。
二、前缀和进阶——二维前缀和
既然能够求解一维数组的区间和，那么我们推而广之，它是否也可以进行矩阵区域的求和呢？答案是肯定的
如上图，这里我们定义每个位置对应s数组储存的是其左上区域所有元素的总和，因此调用上方元素和左方元素，再加上a【i】【j】。但是注意我们的s[i-1][j]和s[i][j-1]其实有一片重合区域——s[i-1][j-1]，他被我们重复计算，因此需要减去其中一个。
所以至此，求区域总和慢慢变得像是一个数学几何问题了，用区域相减相加，再处理重合部分
这里我们求的是坐标（a，b）至（i，j）围成的红色矩形区域的总和，易得:
- s[a][j-1]=BLUE+GREEN;
- s[i-1][b]=ORANGE+GREEN;
- s[a-1][b-1]=GREEN;
- RED=GREEN+BLUE+ORANGE;
联立解得红色区域。
三、前缀和的近亲——差分数组
如果弄清楚了前缀和，那么差分其实也好办了——我们说前缀和计算的是一段区域总和，而差分则是能方便我们快速地将一段区域上的元素同时加减某数。
| 序号 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| 原始数组 a[i] | 0 | 3 | 4 | 5 | 2 | 7 | 12 | 6 |
| 差分数组 d[i] | 3 | 1 | 1 | -3 | 5 | 5 | -6 |
之前我们计算前缀和是用**s[i]=a[1]+a[2]+a[3]+…+a[i]来计算的，目的是为了使a[i]=s[i]-s[i-1]；同理，差分的公式为：d[i](差分数组)=a[i]-a[i-1]，这样就可以保证a[i]=s[1]+s[2]+s[3]+…+s[i]。注意差分数组由于公式中存在a[i-1]，所以也要在原始数组中多添加一项a[0]**防止溢出。
我们在用差分数组计算某一项的值时，都会从最开头累加，因此只要在差分数组上动些手脚，就能实现对区域上的元素同时加减某数。
| 序号 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| 原始数组 a[i] | 0 | 3 | 4+1=5 | 5+1=6 | 2+1=3 | 7 | 12 | 6 |
| 差分数组 d[i] | 3 | 1+1 | 1 | -3 | 5-1 | 5 | -6 |
由于是累加，那么在差分数组某一项上加减，它之后的所有项都会受到加减的buff，直到有一项主动减去来抵消这种影响。