前缀和

讲解

主要分为一维和二维前缀和，作为基础算法为此后众多高级算法提供基础知识。在 O(N)\mathcal O(N) 的预处理后，能够借助差分算法，以 O(1)\mathcal O(1) 的时间复杂度求部分和。

一维——求出数组的某一下标区间内符合要求的元素之和：

二维——求出二维数组某一子矩阵内符合要求的元素之和（通常和DP结合）

题单与部分题解

1. 洛谷P1865 - A % B Problem（源地址自⇔洛谷P1865）

   tag：⇔数论（素数筛）、⇔前缀和、⇔个人评级：入门级（橙题）【原：黄】

   题意：对于给定的区间，输出这段区间内质数的个数（输出给定区间内质数的个数）。

   思路：先一遍 O(n∗n)O(n*\sqrt{n}) 的遍历求解每一位是否是质数，然后再用前缀和数组累加，求出到这一位为止前面一共有多少质数。对于一次询问，以 O(1)O(1) 效率输出。

   补充：刚开始以为数据量是 t∗ntn ，想到朴素素数筛可能过不了（t∗n∗ntn\sqrt{n}），所以就改用了埃氏筛，最终时间复杂度是 O(t+n∗log2n)O(t+nlog_2n) ，用时85ms，看了一圈应该是用时最短的那个层级的了。A了之后才发现 tt 不是乘到复杂度里的，而是加进去的，而且数据很水 （洛谷的数据一如既往的水啊） 。

2. 洛谷P1114 - “非常男女”计划（源地址自⇔洛谷P1114）

   tag：⇔排序、⇔前缀和、⇔个人评级：入门级（橙题）【原：黄】

   题意：找到给定 0101 序列中最长的子串，子串中 00 的数量等于 11 的数量（输出包含 0101 数量相等的最长子串）。

   思路：若有两个位置，其前面 1,01,0 的数量差相同，则说明这两个位置之间 1,01,0 的数量差为0，即为所求。故——先一遍 O(n)O(n) 的遍历计算出前缀和数组，求出到这一位为止前面 11 的数量比 00 的数量多了多少个，并存入类桶结构，然后以常数时间查找、输出（注意，这个地方有卡常风险）。

3. 洛谷P3131 - [USACO16JAN]Subsequences Summing to Sevens S（源地址自⇔洛谷P3131）

   tag：⇔数学规律、⇔前缀和、⇔个人评级：普及级（黄题）【原：橙】

   题意：找到给定序列中最长的子串，子串中各元素之和恰好能被 77 整除（输出各元素之和恰好能被 77 整除的最长子串）。

   思路：其实和上一题一样，但是不那么容易想到。若有两个位置，其前面所有元素之和 %7%7 恰好相等 ，则说明这两个位置之间各元素之和 %7%7 为0，即为所求。先一遍 O(n)O(n) 的遍历计算出前缀和数组，求出到这一位为止前面所有元素之和 %7%7 的值，并存入类桶结构，然后以常数时间（ O(7)O(7) ）查找、输出即可。

4. 洛谷P2969 - [USACO09DEC]Music Notes S（源地址自⇔洛谷P2969）

   tag：⇔二分法、⇔STL、⇔前缀和、⇔个人评级：入门级（橙题）

   题意：（输出给定元素在哪个区间里）。

   参见类似题

5. 洛谷P3662 - [USACO17FEB]Why Did the Cow Cross the Road II S（源地址自⇔洛谷P3662）

   tag：⇔前缀和、⇔差分、⇔个人评级：普及级（黄题）

   题意：共有 nn 个信号灯，坏了 bb 个，给出它们的编号。问：最少修好几个信号灯，使得连续有 kk 个信号灯是好的。

   思路：先处理路灯亮灭，亮为 00 ，灭为 11 。再计算前缀和，求出到这一位为止前面一共有多少 11 （多少灯是灭的）；再差分，求出从前面 kk 位到这一位为止（连续 kk 盏灯），一共有多少 11 （多少灯是灭的），同时统计最小值。

6. 洛谷P3406 - 海底高铁（源地址自⇔洛谷P3406）

   tag：⇔前缀和、⇔贪心、⇔个人评级：入门级（橙题）【原：黄】

   题意：nn 座城市按数序，各自有独立铁路相连，每段铁路的票均分为两种，且价格各不相同——一种是以高价 AiA_i 购买，另一种是先以 CiC_i 办卡（一段铁路只需办一次卡）、再以低价 BiB_i 购买。现告诉你访问城市的顺序，计算出最少的花费是多少。

   思路：先使用前缀和算法，求出每一段铁路分别经过了几次，再根据售价计算最少的花费。全程开销为 O(n+m)O(n+m) 。

7. 洛谷P4440 - [COCI2017-2018#3] Programiranje（源地址自⇔洛谷P4440）

   tag：⇔前缀和、⇔个人评级：入门级（橙题）【原：绿】

   题意：给定序列 StrStr ，共有 kk 次询问，每次取出 Str[l,r] 和 Str[L,R] 两串子串，判定这后者是否可以通过重新排列得到前者。

   思路：转化题意，就是判断两个区间中，每个字母的数量是否相等。对每一个字母进行前缀和，求出到这一位为止前面一共有多少这个字母，然后差分并输出答案。

8. CF1253C - Sweets Eating（源地址自⇔CF1253C）

9. CF816B - Karen and Coffee（源地址自⇔CF816B）

10. CF1547E - Air Conditioners（源地址自⇔CF1547E）

past202010_h - マス目のカット：二维前缀和

O(N3∗10)\mathcal O(N^3*10) ；这题范围较小，直接 O(N5)\mathcal O(N^5) 的暴力也可以过（因为跑不满）。