概念

公式与推导

啥是前缀和？？
前缀和是一个数组的某项下标之前的所有数组元素的和。
通俗的讲，数组中以这个元素为止，向前所有的数的和。在一维内，设前缀和数组为d[],原数组为a[],根据含义我们得到定义式和递推式：

那么我们在对a[]进行O(n)预处理后，就可以O(1)求出区间[i,j]的和sum[i,j]：其推导过程可以通过用d[]等价a[]的某区间和推出，建议手推一下以便于理解，并不难操作。
差分呢？？？
差分是一个数组相邻两元素的差，一般为下标靠后的减去靠前的一个。设差分数组x[],即：
他俩有什么关系？
通过举例带入数组的方法，若用D(a)表示a的前缀和数组，F(a)表示a的差分数组，可以得出：

1.D(x)=a
2.F(d)=a

推导过程与利用区间和求前缀和的公式推导的方法类似，不难操作（以1为例，2与之类似）：

d[i]=a[i]+a[i-1]+a[i-2]+……+a[1],d[i-1]=a[i-1]+a[i-2]+……+a[1];
F(d): x[i]=d[i]-d[i-1]=(a[i]+a[i-1]+a[i-2]+……+a[1])-(a[i-1]+a[i-2]+……+a[1])=a[i];

如果认为D，F是两种运算，那么它们成为逆运算；如果他们是两种函数，那么它们互为反函数。

注意：此处的D，F为本人为方便表述而创造的名词……本人也把前缀和差分运算称为”DFO(DF Operator)”

推广

刚才我们讨论了一维DFO，那么如果把它推广到二维中，是什么样子的呢？

由于我们需要用已求得的d[l][r]来求出d[i][j],所以可以用以下方式预处理出二维前缀和。参照下图，根据容斥原理（多加了的要减回来），得：

类似的，计算sum[l,r][m,n]:

扩展到高维的数组中，我们同样可以类似的求出区间和。就像容斥原理推广到筛法原理一样。

应用

前缀和一般用于加快计算区间和的速度，更重要的应用是前缀和优化DP。
差分可以用于区间修改与查询，可以说是一种RMQ。
若对a的区间[l,r]执行对a[i]+c的操作，我们可以通过x[l]+c,x[r+1]-c进行操作，根据DFO在询问时通过计算D(x)求得更改后的数组a’。具体验证过程推导原理建议大家通过DFO进行模拟。

例题

zzuoj 10471 数列游戏 I
——木有其他的了