浅谈前缀和
jijidawang
2020-03-28 21:33:15
## 引入
如果你想维护一个数据结构，有一个序列 $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](https://www.luogu.com.cn/problem/P1147)。
### [例题1] P1569 【Generic Cow Protests】
- [题目传送门](https://www.luogu.com.cn/problem/P1569)
- [我写的题解](https://www.luogu.com.cn/blog/writeSTL/solution-p1569)
题意简述：
> 将数列 $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
- [题目传送门](https://www.luogu.com.cn/problem/P1865)
题意简述：
> 求区间质数个数。
因为是质数我们可以尝试[埃氏筛](https://baike.baidu.com/item/%E5%9F%83%E6%8B%89%E6%89%98%E6%96%AF%E7%89%B9%E5%B0%BC%E7%AD%9B%E6%B3%95/374984?fromtitle=%E5%9F%83%E6%B0%8F%E7%AD%9B&fromid=5677377&fr=aladdin)，因为是求区间质数个数，所以要 `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 数字游戏
- [题目传送门](https://www.luogu.com.cn/problem/P1043)
题意简述：
> 给定**一圈**整数（一共 $n$个），你要按顺序将其分为 $m$ 个部分，各部分内的数字相加，相加所得的 $m$ 个结果 $\bmod \;10$ 后再相乘，使最终结果最大/最小。
首先对于环状的东西首先当然要破环为链。
我们设 $dp_{i,j,h}$ 为从 $i$ 到 $j$ 分成 $h$ 段的最大/最小值。
我们枚举中间点 $k$，则转移方程如下：
$$dp_{i,j,h}=\max(\mathrm{or} \;\min)\left(dp_{i,j,h},dp_{i,k,h-1}\sum_{p=j}^{k-1}a_i\right)$$
- 循环处注意先枚举区间长度，要不然会有遗漏。
- 再枚举左右端点，区间 dp 套路。
- 然后枚举段数用来更新。
- 最后枚举中间点 $k$。
大约时间复杂度是 $\mathcal{O}(n^3m)$，跑不满的。
### [例题4]P2969 [USACO09DEC]Music Notes S
- [题目传送门](https://www.luogu.com.cn/problem/P2969)
题意简述：
> 给定序列 $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 的求和（~~虽然一般是单调队列优化~~）和某些区间统计问题。