枚举优化算法:前缀和与差分

r-c

1. 前缀数组

题目：给定长度为 $n$ 的数组 $a$ 及其每一项的值，询问 $l$ 到 $r$ 之间的数的和（区间和）。

枚举思路：循环累加 $l$ 到 $r$ 之间每一项即可。但若是询问 $m$ 次，且每次区间都不相同呢？

若仍然采用每次询问都累加的方法，当 $n、m$ 较大时，循环就很耗时了，超出 $1$ 秒就不得分。

前缀数组： $s[i] = a[i] + s[i - 1]$ ， $s、a$ 数组下标均从 $1$ 开始， $0$ 号下标值为 $0$ 。

含义： $s[i]$ 表示 $a[1] + a[2] + a[3] + ... + a[i]$ 的和。那么要计算 $l$ 到 $r$ 之间的区间和，只需要计算 $s[r] - s[l - 1]$ 即可，循环变成了减法，效率提升。

如果求完前缀后原数组无用，也可以直接在原数组上执行 $a[i] += a[i - 1]$ 变为前缀数组。

例题
p643 前缀和

题目：给定长度为 $n$ 的数组及其每一项的值，操作 $l$ 到 $r$ 之间的每个数都加 $1$ （区间操作）。

枚举思路：循环 $l$ 到 $r$ ，每个数都加 1 即可。但若是 $m$ 次操作，且每次操作区间都不同呢？

若仍然采用每次操作都循环的方法，当 $n、m$ 较大时肯定也会超时。

差分数组： $d[i] = a[i] - a[i - 1]，d、a$ 两个数组下标均从 1 开始，0 号下标值为 0。

含义：差分数组存储的是差值， $l$ 到 $r$ 内每个数加上 $m$ ，那么区间内相邻的数间的差值不变，变的只有首尾两个差值。

即： $d[l] += m; d[r + 1] -= m;$

若操作结束后想还原回原数组，只需要对差分数组求前缀和即可。

例题
p644 差分

例题
abc281c C - Circular Playlist

前缀数组适合求区间和，差分数组适合处理区间操作。

前缀数组的差分数组是原数组，差分数组的前缀数组的原数组。

例题
P276子矩阵求和