作者:whisper
链接:https://www.proprogrammar.com/article/1016
声明:请尊重原作者的劳动,如需转载请注明出处
前缀和是一种查询数组中任意区间的元素的和的数据结构,这里数组给定之后就不变了。针对这个不变的数组,前缀和用于多次查询区间 [i, j] 上元素的和。
对于动态规划而言,前缀和的意义主要有两点:
此之外,一些问题需要前缀和与其它数据结构配合来解决,也有两类:
前缀和的推导和计算隐含着动态规划的基本思想,同时它的状态设计是线性动态规划中比较简单的那一类。与线性动态规划一样,前缀和也有一维和二维两种场景。
虽然前缀和本身很简单,但需要用到它解决的问题非常多,与其它数据结构配合的变化也很多,因此需要从线性动态规划中剥离出来单独学习。
考虑以下问题:
有两类在数组 a 上的求和需求
对于前缀和,S[i + 1] 刚好就是答案,因为这就是前缀和的定义:
对于区间和,解决此问题最直观的方法是枚举 [L, R] 上的所有元素求和:
这种方法虽然直观,但是不足是查询一次需要 O(N) 的时间,并且每来一个新的查询,就要重新枚举元素求和。通过简单的画图推导可以得到答案为 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<=n−1) 的和,这一系列的和都是从 0 开始的,因此称为前缀和。公式如下:
此后的区间查询都可以利用公式 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) 的。
以上就是前缀和的基础介绍了,其中比较关键的有两点
前缀和除了求区间和之外,还有一些其它的应用:
利用前缀和求区间和的思想,已经求前缀和的过程在上一节中已经重点介绍,这里主要回顾一下前缀和中的动态规划思想,如下:
状态定义: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[i] 对应的前缀和 S[i+1], 在插入到 unordered_set 之前先问:S[i+1] - target 在 unordered_set 中是否出现。
如果出现,说明存在以 i 结尾的某个区间,和为 target, 则找到答案。
如果不出现,则没有以 i 结尾的区间,和为 target,继续枚举 i + 1
上面的问题还可以有变种:
按照第一问的思路,把 unordered_set
改成 unordered_map
就可以
参考题目:560. 和为 K 的子数组
整体思路与第一问相同,但是维护前缀和的数据结构需要从哈希表变为线段树
参考题目:327. 区间和的个数
这是第一问的树形版本,dfs(前序遍历)时,栈里存的是当前节点到根的链,这条链上的和可以作为前缀和维护在 unordered_map 里。从左子树跳到右子树的时候,左子树的所有节点对应的前缀和要先从 unordered_map 中删掉。
参考题目: 437. 路径总和 III
数据结构维护前缀和相关练习题:
以下若干组题目都是利用数据结构维护前缀和,实现统计数组中的某个指标的目的。
HashMap 维护(1),键是前缀和(状态)的值,值为第一次出现时的索引。
HashMap 维护(2),键是前缀和(前缀状态)的值,值为出现次数。
HashMap 维护(3),键是前缀和模 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 。
例如:
在力扣上有一些这种类型的题目,见后续节。
运算推广相关练习题:
前面提到,前缀和的加法运算可以推广到其它运算,并高效地利用前缀上的结果计算区间上的结果,只需要该运算满足区间减法。
这类运算常见的是乘法和异或。
差分序列的好处是如果要对原序列的一个区间 [l, r] 上所有值加 val,原序列上要操作 r-l+1 次 (a[l .. r] + val),在差分序列上只需要操作 2 次(b[l] + val, b[r+1] - val)。如果这种区间操作需要很多次,最后的查询只有一次的话,就非常适合在差分序列上操作。
在力扣上有一些这种类型的题目,见本章下一节。
利用这个性质,可以高效第维护一些区间操作,例如区间加法。下面这一题就是在差分序列上维护区间操作的典型题。
亲爱的读者:有时间可以点赞评论一下
月份 | 原创文章数 |
---|---|
202205 | 1 |
202204 | 1 |
202203 | 11 |
202201 | 2 |
202108 | 7 |
202107 | 3 |
202106 | 16 |
202105 | 10 |
202104 | 16 |
202103 | 56 |
202102 | 14 |
202010 | 3 |
202009 | 3 |
202008 | 7 |
202007 | 7 |
202006 | 10 |
202005 | 11 |
202004 | 22 |
202003 | 52 |
202002 | 44 |
202001 | 83 |
201912 | 52 |
201911 | 29 |
201910 | 41 |
201909 | 99 |
201908 | 35 |
201907 | 73 |
201906 | 121 |
201811 | 1 |
201810 | 2 |
201804 | 1 |
201803 | 1 |
201802 | 1 |
201707 | 1 |
全部评论