数据结构与算法 - 动态规划（前缀和）

发表于 2020-10-05 更新于 2021-11-07 分类于数据结构与算法

转载说明

作者：力扣 (LeetCode)
链接：https://leetcode-cn.com/leetbook/read/dynamic-programming-1-plus/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

前缀和是一种查询数组中任意区间的元素的和的数据结构，这里数组给定之后就不变了。针对这个不变的数组，前缀和用于多次查询区间 [i, j] 上元素的和。

对于动态规划而言，前缀和的意义主要有两点：

一维和二维前缀和的推导，分别用到了单串和矩阵中最经典的状态设计以及状态转移；
在一些更复杂的动态规划问题中，状态转移的时候需要依赖区间和，因为状态转移是非常频繁的操作，因此必须高效地求区间和才能使得状态转移的时间复杂度可接受，此时就必须用到前缀和了。

除此之外，一些问题需要前缀和与其它数据结构配合来解决，也有两类：

先预处理出前缀和数组，这一步是动态规划，然后在前缀和数组上用其它数据结构解决；
还是按照动态规划的方式求前缀和，也需要额外的数据结构维护前缀和，但不是预处理好前缀和数组之后再用数据结构计算，而是每求出一个前缀和，就更新一次数据结构并维护答案。

前缀和的推导和计算隐含着动态规划的基本思想，同时它的状态设计是线性动态规划中比较简单的那一类。与线性动态规划一样，前缀和也有一维和二维两种场景。

虽然前缀和本身很简单，但需要用到它解决的问题非常多，与其它数据结构配合的变化也很多，因此需要从线性动态规划中剥离出来单独学习。

前缀和简介

考虑以下问题：

给定长度 n 的序列 a：\(a_{0}, a_{1}, ..., a_{n-1}\)，给每个前缀求一次和，\(S_{0} = 0\), \(S_{i}=\sum_{j=0}^{i-1}a_{j}\)。这些前缀和维护在一个长度 \(n + 1\) 数组 S 里, 称为前缀和数组。

有两类在数组 a 上的求和需求

前缀和：求 a[0..i] 的和
区间和：求区间 a[L, R] 的和

对于前缀和，S[i + 1] 刚好就是答案，因为这就是前缀和的定义：\(S_{i + 1}=\sum_{j=0}^{i}a_{j}\)。

对于区间和，解决此问题最直观的方法是枚举 [L, R] 上的所有元素求和：\(sum(L, R) = \sum_{idx = L}^{R}nums[idx]\)。

这种方法虽然直观，但是不足是查询一次需要 O(N) 时间，并且每来一个新的查询，就要重新枚举元素求和。通过简单的画图推导可以得到答案为 S[R + 1] - S[L]S[R+1]−S[L]

如果查询次数很多，当新查询来时，此前的查询计算的中间结果很多是可以直接用的，新的查询不必重新枚举，例如此前查询过 sum(5, 10)，现在来了新查询 sum(4, 8) 在计算新查询时，5 ~ 8 这一段在计算此前的查询 sum(5, 10) 的时候已经计算过了，新查询的计算过程可以写成 nums[4] + sum(5, 8)，而不用全部枚举。

如果已经有了前缀和数组，那么通过简单的画图推导可以知道，两个前缀和 S[R+1] 和 S[L] 的差刚好就是 [L, R] 上的区间和。已有前缀和数组之后，这一步操作就是 O(1) 的。

现将前缀和数组预处理出来，然后在每次查询中直接通过前缀和数组来计算而不是通过原数组，这是一种缓存中间结果的思想，如果把这一思想执行彻底，可以将所有可能的问题 sum(i, j) 其中 0 <= i <= j <= n-1，将计算它们所需的所有中间结果先算一次缓存下来。这里提到的是缓存所有所需的中间结果，而不是子问题的中间结果，因为计算 sum(i, j) 需要的中间结果是前 i-1 个数的和 sum(0,i) 和前 j 个数的和 sum(0, j+1)。最终 sum(i, j) = sum(0, j+1) - sum(0, i) 这对于所有的区间查询都是适用的。

以上将中间结果缓存思路与动态规划中缓存子问题的解的思路是一致的。

定义 sums[k] 为 [0..k-1] 的和，其中 sums[0] 表示数组中没有数字被选中，sums[1] 表示之选中第一个数 nums[0]。预先计算 0 ~ k (0 <= k <= n-1) 的和，这一系列的和都是从 0 开始的，因此称为前缀和。公式如下：

k = 0 : \(sum(0,0)=0\)
1 <= k <= n-i : \(sum(0,k) = \sum_{i=0}^{k-1}nums[i]\)

此后的区间查询都可以利用公式 sum(i, j) = sums(0, j + 1) - sum(0, i)

在上一章中，我们把线性动态规划中几种主流问题及其对应的 dp 状态设计做了总结。其中最基础的一种是单串 dp[i]，并且只与子问题 i - 1 有关，即 dp[i] = f(dp[i-1])。前缀和就是这种情况，sums[i] 只与 sums[i-1] 有关。推导前缀和数组的过程是 O(N) 的，如果区间和的查询次数达到了 O(N) 那么计算区间和的时间复杂度是摊销 O(1) 的。

以上就是前缀和的基础介绍了，其中比较关键的有两点

预处理前缀和的过程是最简单且最经典的单串动态规划问题。
先将所有位置的前缀和预处理出来，然后再处理区间和的查询，这是一种先缓存中间结果再处理查询的思路，因为这些中间结果在查询时需要反复用到，缓存之后就不用反复计算了，因此花时间预处理这些信息是有效的。

前缀和除了求区间和之外，还有一些其它的应用：

在用 dp 的方式推 sums[i] 的时候，有时求完 sums[i] 需要查询以前算过的结果计算某种指标，需要用其它数据结构将前面的计算结果维护起来，例如哈希表等等，在求每个位置的前缀和的过程中，查询数据结构并更新答案，这是前缀和的一大类问题，变化比较多，力扣上这类题也有很多，在本章最后一节中汇总了一些题目，在下一节也选择了典型题目做讲解。
前缀和的逆运算是差分，对原序列求出其差分序列，然后在对得到的差分序列求其前缀和序列，可以得到原序列，这在处理一些区间修改的问题时很有用，参考后面小节的题目讲解。
前缀和还可以推广到二维上，并用于快速求矩形和，二维前缀和的计算过程是最经典的矩阵上的线性动态规划，参考后面一节的题目和讲解。

求区间和

利用前缀和求区间和的思想，已经求前缀和的过程在上一节中已经重点介绍，这里主要回顾一下前缀和中的动态规划思想，如下：

状态定义：sums[i] := [0..i-1] 的和
状态转移：sums[i] = a[i - 1] + sums[i - 1]
初始化：sums[0] = 0

这是最简单的单串线性动态规划，其思想在上一章重点介绍。求解该动态规划问题后得到数组 sums 。然后区间和问题就变成了两个前缀和的差的问题。

int rangeRum(int L, int R)
{
    return sums[R + 1] - sums[L];
}

求区间和相关练习题

实现前缀和问题
- 区域和检索 - 数组不可变
- 二维区域和检索 - 矩阵不可变

数据结构维护前缀和

在上一节中提到，在用 dp 的方式推 sums[i] 的时候，有时求完 sums[i] 需要查询以前算过的结果计算某种指标，需要用其它数据结构将前面的计算结果维护起来，以便高效查询。以下几个问题就是以上思路的直接应用。

将前缀和维护在数据结构中，以便于后续的多次查询，最常见的是维护在哈希表中。

力扣上这种题目非常多，更多题目详见本章后续节。下面考虑几个经典问题：

第一问：\(a_{0}, a_{1}, ..., a_{n-1}\) 上有没有一个区间，其和为 target。计算前缀和数组 sums[i] 。当扫描到 i 时，\(a_{0}, a_{1}, ..., a_{i-1}\) 的前缀和都已经求过了，在计算的过程中将前缀和维护在数据结构中，以便于后续的多次查询，本题在之后要查询前缀和的值是否存在，因此维护在 unordered_set 里。

求完当前值 a[i] 对应的前缀和 S[i+1], 在插入到 unordered_set 之前先问：S[i+1] - target 在 unordered_set 中是否出现：

如果出现，说明存在以 i 结尾的某个区间，和为 target, 则找到答案。
如果不出现，则没有以 i 结尾的区间，和为 target，继续枚举 i + 1。

上面的问题还可以有变种：

第二问：\(a_{0}, a_{1}, ..., a_{n-1}\) 上有多少个区间，其和为 target。

按照第一问的思路，把 unordered_set 改成 unordered_map 就可以

参考题目：560. 和为 K 的子数组

第三问：\(a_{0}, a_{1}, ..., a_{n-1}\) 上有没有一个区间，其和大于或小于 target。

整体思路与第一问相同，但是维护前缀和的数据结构需要从哈希表变为线段树

参考题目：327. 区间和的个数

第四问: 一棵树上有没有某个路径，其和为 target。

这是第一问的树形版本，dfs（前序遍历）时，栈里存的是当前节点到根的链，这条链上的和可以作为前缀和维护在 unordered_map 里。从左子树跳到右子树的时候，左子树的所有节点对应的前缀和要先从 unordered_map 中删掉。

参考题目： 437. 路径总和 III

数据结构维护前缀和相关练习题

HashMap 维护 (1)，键是前缀和（状态）的值，值为第一次出现时的索引
- 和等于 k 的最长子数组长度
- 连续数组
- 每个元音包含偶数次的最长子字符串 —— 前缀状态为 a,e,i,o,u 的个数的奇偶
HashMap 维护 (2)，键是前缀和（前缀状态）的值，值为出现次数
- 和为 K 的子数组
- 统计优美子数组 —— 前缀状态为奇数的个数
HashMap 维护 (3)，键是前缀和模 K 的余数（可以理解为前缀状态，状态为前缀和模 K）
- 连续的子数组和 —— 值为第一次出现时的索引
- 和可被 K 整除的子数组 —— 值为出现次
前缀和（积）与后缀和（积）均需要
- 除自身以外数组的乘积
- 寻找数组的中心索引
- 找两个和为目标值且不重叠的子数组 —— 前缀和后缀和分别推一次，推的时候保存信息（DP），枚举分割点
二维前缀和
- 元素和为目标值的子矩阵数量
- 矩阵区域和
- 最大子矩阵 —— 思路类似一维的最大子数组和
- 矩形区域不超过 K 的最大数值和 —— 在上一题基础上加了一个 K

运算推广

前缀和求的是数组 a 的前缀 [0..i-1] 的和，也就是对这些元素做加法结果，实际上对前缀 [0..i-1]，我们还可以做很多其它运算得到相应结果。如果利用前缀上的某种运算的结果，可以像前缀和一样快速得到区间 [L, R] 上同样运算的结果，那么前缀和就成功推广了。

事实上这种运算是存在的，例如异或运算，对应每个前缀 [0..i-1] ，我们都可以求得一个异或值，称为前缀异或，而对于区间 [L, R]。我们可以用 [0..R] 的前缀异或减去 [0..L-1] 的前缀异或就可以得到区间上的异或值，这个逻辑与前缀和完全相同。这依赖于异或运算的性质。

如果想将某种运算应用到前缀元素上，并且利用前缀的结果快速计算区间结果，需要该运算满足区间减法：区间 A = [i, j]，区间 B = [i, k] 区间 C = [k+1, j]，那么有了大区间 A 上的结果 a 和其中一个小区间 B 上的结果 b, 要能够算出另一个小区间 C 上的结果 c 。

例如：

异或：\(a = b \oplus c => c = b \oplus a\)
乘法或模下乘法：\(a = b \times c => c = a / b\)

运算推广相关练习题

前缀和乘积最大子数组乘积小于 K 的子数组最后 K 个数的乘积 —— 若乘法的前缀积会溢出，可以用对数的前缀和防溢出，但是结果转回整数需要用四舍五入而不是下取整
前缀异或子数组异或查询形成两个异或相等数组的三元组数目 —— 哈希表维护前缀异或结果，类似「560. 和为 K 的子数组」

差分

前缀和序列 \(S_{0}, S_{1}, ..., S_{n}\) 的差分序列 \(a_{0}, a_{1}, ..., a_{n-1}\) 就等于原序列，其中 \(a_{i} = S_{i+1} - S_{i}\) 原序列 \(a_{0}, a_{1}, ..., a_{n-1}\) 的差分序列为 \(b_{0}, b_{1}, ..., b_{n-1}\)，其中 \(b_{0} = a_{0} - 0\), \(b_{i} = a_{i} - a_{i-1}\) 则对差分序列求前缀和序列，就得到原序列。

差分序列的好处是如果要对原序列的一个区间 [l, r] 上所有值加 val，原序列上要操作 r-l+1 次 (a[l .. r] + val)，在差分序列上只需要操作 2 次 (b[l] + val, b[r+1] - val)。如果这种区间操作需要很多次，最后的查询只有一次的话，就非常适合在差分序列上操作。

差分相关练习题

区间加法 —— 用差分维护区间加法模板

何照江的博客