引入
如果你想维护一个数据结构，有一个序列 \(a\)，每次查询 \(l\sim r\) 区间和（求 \(\sum\limits_{i=l}^ra_i\)），只有查询，线段树&树状数组难免有些大材小用，但是维护它效率要高，甚至要达到 \(\mathcal{O}(1)\)。
这个东西该怎么维护呢？
我们可以创造一个序列 \(s_i=\sum\limits_{j=1}^ia_i\)。
这个序列显然可以用一种递归方式定义：
\(s_i=\begin{cases} a_i&i=1\\ s_{i-1}+a_i&i>1 \end{cases}\)
这样的话每次查询只需要输出 \(s_{r}-s_{l-1}\) 就行了。
\(s\) 在输入时即可统计，不会增加太多常数。
这种创造 \(s\) 数组的方法叫做前缀和，\(s\) 叫做对于 \(a\) 的前缀和。
应用
当然前缀和在区间求和应用领域极其有用，对于前缀和的求和性质，我们可以优化一些题目，比如 P1147。
[例题1] P1569 【Generic Cow Protests】
题意简述：
将数列 \(a\) 分成几组，每组数字和 \(\ge 0\) ，求最大组数。
我们维护一个数组 \(dp_i\) 表示区间 \(1\sim i\) 之间的最优解，我们找到两个数 \(i,j\)，统计 \(a_i+a_{i+1}+a_{i+2}+\dots+a_{j-1}+a_j=\sum\limits_{k=i}^ja_i\)，然后更新最优解即可，注意判断不可行情况 \(dp_j<0\) 即可。
这个算法的时间复杂度是 \(\mathcal{O}(n^3)\) 的，显然会 TLE，我们该怎么优化呢？
我们发现，只有求和是可以优化的，我们就可以考虑维护一个前缀和数组，\(\mathcal{O}(1)\) 解决求和问题，算法时间复杂度直接降到 \(\mathcal{O}(n^2)\)
通过这道例题我们发现前缀和真是个有用的工具，它主要用来优化区间求和问题。
[例题2] P1865 A % B Problem
题意简述：
求区间质数个数。
因为是质数我们可以尝试埃氏筛，因为是求区间质数个数，所以要 for 遍历一遍，\(m\le 10^6\)，时间复杂度是 \(\mathcal{O}(m\log \log m+n^2)\approx\mathcal{O}(n^2)\)。
\(\mathcal{O}(m\log \log m)\) 已经很接近线性了，主要是优化 \(\mathcal{O}(n^2)\) 部分。
我们可以维护一个序列 \(p\) 表示 \(1\sim p\) 质数个数，这个埃氏筛时即可解决。
然后求区间质数个数只需要按照前缀和方法相减即可，\(\mathcal{O}(n^2)\to\mathcal{O}(1)\)！，时间复杂度立刻降到 \(\mathcal{O}(m\log \log m)\approx\mathcal{O}(m)\)。
[例题3] P1043 数字游戏
题意简述：
给定一圈整数（一共 \(n\)个），你要按顺序将其分为 \(m\) 个部分，各部分内的数字相加，相加所得的 \(m\) 个结果 \(\bmod \;10\) 后再相乘，使最终结果最大/最小。
首先对于环状的东西首先当然要破环为链。
我们设 \(dp_{i,j,h}\) 为从 \(i\) 到 \(j\) 分成 \(h\) 段的最大/最小值。
我们枚举中间点 \(k\)，则转移方程如下：
- 循环处注意先枚举区间长度，要不然会有遗漏。
- 再枚举左右端点，区间 dp 套路。
- 然后枚举段数用来更新。
- 最后枚举中间点 \(k\)。
大约时间复杂度是 \(\mathcal{O}(n^3m)\)，跑不满的。
[例题4]P2969 [USACO09DEC]Music Notes S
题意简述：
给定序列 \(a\)，有序列 \(b\)：\(b_0\sim b_{a_1-1}=1\)，\(b_{a_1}\sim b_{a_1+a_2-1}=2\)，\(b_{a_1+a_2}\sim b_{a_1+a_2+a_3-1}=3\)，\(\dots\)，询问 \(q\) 次 \(b_i\)。
这个维护一个前缀和标记极值，然后 upper_bound 即可解决，很简单。
时间复杂度大概是 \(\mathcal{O}(q\log n)\)。
总结
前缀和主要应用于优化区间求和，对于形如\(\sum\limits_{i=l}^ra_i\) 的柿子可以优化到 \(\mathcal{O}(1)\)，做题时主要应用于 dp 的求和（虽然一般是单调队列优化）和某些区间统计问题。
京公网安备 11010502036488号