前缀和与差分是两个简单且实用的技巧，可以降低对序列的操作的复杂度，今天就来学习一下它们

前缀和

前缀和已经在 贪心算法一本通平台详解 中 P1224：最大子矩阵 中提到过了

前缀和可以利用  的时间处理数据，完成后每次询问仅需  的时间复杂度求解任意区间内的和，相比之下，要比暴力求解长度为  的区间和 (  ) 快得多

下面规定  为前缀和数组， 为原数组， 为指定求和的区间左右端

一维前缀和

前缀和最重要的就是前缀和数数组 ， 记录着  到  的和，但是我们需要的是 的值，那应该如何做呢

相比之下，不难发现当  时， 中记录的值多了  这一部分，而一段的和也是能够通过前缀和求出的，所以

前缀和很巧妙地将任意一段区间的和转换为了两段区间的和的差，从而大大降低了时间复杂度

如图示中，1 操作中绿色的区间就是从 1~R 的和，2 操作中红色的区间就是从 1~L-1 的和，3 操作中将红色部分从绿色部分减去，最终就剩下了区间 L~R

在计算时并不需要对于每一个  都重新从  开始计算区间和，可以通过上一个区间和加上本次的值得到对应的区间和

一维前缀和完全没有什么难度，所以就会有一些弊端，如  可能会超出整型甚至是长整型的范围

二维前缀和

相比于一维前缀和，二维前缀和更加复杂，但是其原理仍然相同

同样的，给出两个位置  和 ，要求出两点所圈起来的矩形中包含的所有元素的和，如下图求绿色区域的和

根据一维差分不难想到， 记录的应该是，但是这次就不能像一维前缀和一样简单的加减来求出某个区域内的和了

下面将矩形ACBD区域内的和记作 ，其他矩形亦然

观察上图，不难发现下面的式子

可是其中除了  和  以外其他还需要继续分解，将其继续分解得到

合并后得到

注意到式子右侧的字母都是以  开头的，说明其可以通过前缀和求得

形象地表达就是将 蓝色+红色+橙色+绿色 的部分减去 蓝色+红色 部分再减去 蓝色+橙色 部分最后再加上 蓝色 部分，其中每一个部分都可以通过前缀和数组  直接访问，所以

同样地，在计算时也可以通过已计算出的数据来计算新的位置的值，因为按照从左到右，从上到小的顺序进行计算，所以可以保证上方和左方是有正确的数据的，所以根据上面的公式，可以得到计算   区域的公式

差分

前缀和 ( 一维 ) 是利用  和  来求取 的算法

那反过来，要将区间 到  的所有元素都加上 ，能不能也是用  和  来解决呢

既然前缀和是先预处理就能够非常方便地求出区间和，那差分就先修改标记 ( 标记标在差分数组  上 )，最后再来处理和

下面规定  为差分数组， 和  为修改范围， 为修改值

于是我们可以这样进行操作，在需要修改的区间的头和尾分别打上标记  和  的标记，即将  加上 ，将  减去

在最后处理的过程中，设置一个偏差值 ，初始值为 ，表示接下来的数据没有任何偏差，如果遇上差分标记时，更改偏差值，表示接下来的标记有着  的偏差

但是看了下面的代码你就会发现事实上我们并没有设置偏差值 

我们将偏差值  存入了原数组  中，并通过依次继承，让偏差值一直存在于原数组  中，所以就无需设置专门的偏差值  了

好了，那么这篇文章就讲到这里了，如果你觉得本文对你有所帮助，请不要忘记三连支持！