前缀和

经常需要求某序列的区间和，如果直接求一次，时间复杂度为 $O(n)$，多次会超时，当遇到求区间和问题，可以利用前缀和优化。

前缀和定义：$sum[i]=a[1]+a[2]+\dots+a[i]$

可以得到递推关系：$sum[i]=sum[i-1]+a[i]$ (注意：令$sum[0]=0$,$sum[1]=sum[0]+a[1]=a[1]$) ，利用递推关系 $O(n)$ 求出数组所有前缀和。

利用预先计算的前缀和 $sum[i]$,可以在 $O(1)$ 的时间复杂度内求出任意区间和，即 $a[l]+\dots+a[r]=sum[r]-sum[l-1]$ ,本质上是“利用空间，优化时间”。

例题：P2280 [HNOI2003] 激光炸弹

tips: 二维前缀和+容斥

---

差分

前缀和的一个应用是差分，差分是前缀和的逆运算。

一维差分

问题引入：$(1)$ 给定一个长度为$n$的一维数组 $a[]$,数组内每个元素初始值给定；$(2)$ 修改操作：做 $q$ 次区间修改,每次修改对区间内每个元素增加一个值 $d$,即第 $i$ 次修改把数组 $[l_i,r_i]$ 内所有元素加上 $d_i$。 $(3)$ 询问操作：询问一个元素的新值的值。

如果暴力修改一次，$q$ 次修改的时间复杂度为 $O(nq)$,可以利用差分数组优化，时间复杂度改为 $O(q+n)$.

一维差分定义：$b[i]=a[i]-a[i-1]$

$ \left.\begin{matrix}b[1]=a[1]-a[0] \\b[2]=a[2]-a[1] \\b[3]=a[3]-a[2] \\\dots \\b[i]=a[i]-a[i-1] \end{matrix}\right\} $ 相加可得：$b[1]+b[2]+\dots+b[i]=a[i]-a[0]$

当 $a[0]=0$ 时， $\sum_{j=1}^{i}b[j]=a[i]$ ,即差分数组前缀和就是原数组。

原数组区间修改，对于原数组 $a[]$ 区间 $[l,r]$ 内每个元素加上 $d$，差分数组只在端点处修改：

b[l]+=d
b[r+1]-=d

一维差分缺陷：“区间修改+单点查询”，必须先进行“区间修改”，之后才能“单点查询”。如果“修改”和“查询”交叉进行，就需要使用树状数组和线段树进行。

例题 打车

例题P1083 借教室

二维差分

二分差分定义：

$d[i][j]=a[i][j]-a[i-1][j]-a[i][j-1]+a[i-1][j-1]$

同理二维差分数组前缀和，就是原始数组,即：

$a[i,j]=\sum_{x=1}^{i} \sum_{y=1}^{j}d[x][y]$

区间修改：对原数组 $a[][]$,左上角坐标 $(x_1,y_1)$ 至右下角 $(x_2,y_2)$ 所有的元素都加上 $d$，暴力修改一次时间复杂度为 $O(nm)$，差分数组只需要在 $4$ 个端点处修改。

d[x1][y1]    +=d
d[x1][y2+1]   -=d
d[x2+1][y1]   -=d
d[x2+1][y2+1]  +=d

再进行二维前缀和运算 $a[i][j]=a[i-1][j]+a[i][j-1]-a[i][j]+d[i][j]$

例题 P3397地毯

---