前缀和常用于快速地求解区间范围内的元素总和。

设元素存储在a[N]中，我们设计一个数组s[N]，s[i]对应第一个元素到第i个元素的总和，即?[?]=?[1]+?[2]+...+?[?]$s\left[i\right]=a\left[1\right]+a\left[2\right]+...+a\left[i\right]$。

一维前缀和的维护公式为：?[?]=?[?−1]+?[?]$s\left[i\right]=s[i-1]+a\left[i\right]$。

若我们想快速求出区间[?,?]$[L,R]$范围内的元素总和。

我们可以利用前缀和快速求解：???[?,?]=?[?]−?[?−1]$su{m}_{[L,R]}=s\left[R\right]-s[L-1]$。

可通过图片加深理解。

设元素存储在a[N][N]中，我们设计一个数组s[N][N]，用来存储a[1][1]开始的矩阵总和。

s[i][j]的含义可看下图。a[N][N]为无色部分，s[N][N]为深色部分。

那么如何维护二维的前缀和数组呢？可观察下图：

可发现s[i][j]的面积由橙色区域s[i-1][j]与蓝色区域s[i][j-1]组成后，再去掉重叠部分紫色区域s[i-1][j-1]后加上本身位置的内容a[i][j]得到。

故得到公式：?[?][?]=?[?−1][?]+?[?][?−1]−?[?−1][?−1]+?[?][?]$s\left[i\right]\left[j\right]=s[i-1]\left[j\right]+s\left[i\right][j-1]-s[i-1][j-1]+a\left[i\right]\left[j\right]$。

若我们想快速的求出某个子矩阵的元素和，可进行如下处理。

我们设子矩阵左上位置为(xa,ya)，右下位置为(xb,yb)。从而确定子矩阵的形状。

观察下图，可以发现，子矩阵的总和可由红色区域s[xb][yb]去掉蓝色区域s[xb][ya-1]和橙色区域s[xa-1][yb]后，再加上重复减的紫色区域s[xa-1][ya-1]后得到。即，公式为：???子矩阵=?[??][??]−?[??][??−1]−?[??−1][??]+?[??−1][??−1]$su{m}_{子矩阵}=s\left[xb\right]\left[yb\right]-s\left[xb\right][ya-1]-s[xa-1]\left[yb\right]+s[xa-1][ya-1]$。

差分常用于对连续的某个区域快速进行增加和减少的值的操作。

设元素存储在a[N]中，我们设计一个差分数组b[N]，b[i]对应a[i]与a[i-1]的差值,即?[?]=?[?]−?[?−1]$b\left[i\right]=a\left[i\right]-a[i-1]$。

若我们对差分数组b进行前缀和处理，可发现存在逆元特性，前缀和的内容等于原数组a的内容。

s[1]=b[1]=a[1]
s[2]=s[1]+b[2]=a[1]+a[2]-a[1]=a[2]
s[3]=s[2]+b[3]=a[2]+a[3]-a[2]=a[3]
    ...
s[i]=s[i-1]+b[i]=a[i-1]+a[i]-ba[i-1]=a[i]

若我们对b[i]的对加上x。

再进行前缀和处理。

可发现，相当于从i到最后的n，对所有的原数组内容加上了x。

故，若想对[?,?]$[L,R]$的范围的值都加上x。可通过三步实现。

1. b[L]+=x
2. b[R+1]-=x
3. 前缀和处理查分数组b

设元素存储在a[N][N]中，我们设计一个差分数组b[N][N]，用来存储a数组中相邻元素的差值。

二维差分维护公式为：?[?][?]=?[?][?]−?[?][?−1]−(?[?−1][?]−?[?−1][?−1])=?[?][?]−?[?][?−1]−?[?−1][?]+?[?−1][?−1]$b\left[i\right]\left[j\right]=a\left[i\right]\left[j\right]-a\left[i\right][j-1]-\left(a\right[i-1\left]\right[j]-a[i-1\left]\right[j-1\left]\right)=a\left[i\right]\left[j\right]-a\left[i\right][j-1]-a[i-1]\left[j\right]+a[i-1][j-1]$。

若我们对差分数组b进行前缀和处理，存在逆元特点，前缀和结果为原数组a中的内容。

若我们对差分数组b[xa][yb]+=x，再对差分数组求前缀和。可发现，(xa,ya)到(n,n)的原数组内容都加上了x。

若我们想快速地对某个子矩阵区域的元素和加减值。

我们设子矩阵左上位置为(xa,ya)，右下位置为(xb,yb)。从而确定子矩阵的形状。

观察下图

可发现若想对子矩阵区域加上x，可先将红色区域b[xa][ya]加上x，在将橙色区域b[xa][yb+1]与蓝色区域b[xb+1][ya]减去x进行抵消，再将重复减去的紫色区域b[xb+1][yb+1]的内容加上来。

1. b[xa][ya]+=x
2. b[xa][yb+1]-=x
3. b[xb+1][ya]-=x
4. b[xb+1][yb+1]+=x

之后再对差分数组进行前缀和处理即可。

习题代码在项目OIAlgorithm中。

P1115 最大子段和

P1719 最大加权矩形

P2367 语文成绩

P3397 地毯

__EOF__