<style> .reveal p{ text-align:left; } </style> <script> var allLinks = document.querySelectorAll('a'); allLinks.forEach(function(link) { link.target = '_blank'; }); </script> # 枚举优化算法之 # 前缀和与差分 || |:---:| || --- ## 1. 前缀数组 **题目**：给定长度为 $n$ 的数组 $a$ 及其每一项的值，询问 $l$ 到 $r$ 之间的数的和（区间和）。 | 例题| |---| |[p643 前缀和](http://39.99.183.126:8888/p/643)| <script> var allLinks = document.querySelectorAll('a'); allLinks.forEach(function(link) { link.target = '_blank'; }); </script> --- **枚举思路**：循环累加 $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]$ 变为前缀数组。 --- ## 2. 差分数组 **题目**：给定长度为 $n$ 的数组及其每一项的值，操作 $l$ 到 $r$ 之间的每个数都加 $1$（区间操作）。 | 例题| |---| |[p644 差分](http://39.99.183.126:8888/p/644)| --- **枚举思路**： 循环 $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;$ --- 若操作结束后想还原回原数组，只需要**对差分数组求前缀和**即可。 --- ## 3. 前缀差分总结 |例题| |---| |[**abc281c** C - Circular Playlist](http://39.99.183.126:8888/p/abc281c)| --- 前缀数组适合求区间和，差分数组适合处理区间操作。 前缀数组的差分数组是原数组，差分数组的前缀数组的原数组。 --- ## 练习 |练习题| | ----- | |[P153小 X 与煎饼达人(flip)](http://39.99.183.126:8888/p/153)| |[P275计算能力](http://39.99.183.126:8888/p/275)| |[P277倒水](http://39.99.183.126:8888/p/277) | |[P680语文成绩](http://39.99.183.126:8888/p/680)| --- ## 进阶 ### 二维前缀和和差分 [前缀和 & 差分 - 二维前缀和](https://oi-wiki.org/basic/prefix-sum/#%E4%BA%8C%E7%BB%B4%E5%A4%9A%E7%BB%B4%E5%89%8D%E7%BC%80%E5%92%8C) |例题| |---| |[P276子矩阵求和](http://39.99.183.126:8888/p/276)| --- ### 等差数列差分（选修）