type
status
date
slug
summary
tags
category
icon
password
Email
文章首发于：My Blog 欢迎大佬们前来逛逛
前缀和
前缀和是一种常见的算法，用于快速计算数组中某一段区间的和。前缀和的思想就是预处理出数组中前缀和，然后用后缀和减去前缀和，即可快速计算区间和。
以一维数组为例，设 a_i 表示数组中第 i 个元素的值，sum_i 表示数组中前 i 个元素的和，即： sum_i = \sum_{j=1}^{i} a_j 则对于区间 [l, r] 的和可以表示为： \sum_{i=l}^{r} a_i = sum_r - sum_{l-1} 这里需要注意的是，我们需要在原数组的前面插入一个值为 0 的元素，这样才能计算出 sum_0，也就是前 0 个元素的和。 以下是一维前缀和的代码实现：
二维前缀和
对于二维数组，我们可以先对每一行进行一维前缀和，然后对每一列进行一维前缀和，即可得到二维前缀和数组。 设 a_{i,j} 表示二维数组中第 i 行第 j 列的元素值，sum_{i,j} 表示以 (i,j) 为右下角的矩阵的元素和，则有： sum_{i,j} = \sum_{k=1}^{i} \sum_{l=1}^{j} a_{k,l} 则对于矩阵 [x1,y1,x2,y2] 的元素和可以表示为： \sum_{i=x1}^{x2}\sum_{j=y1}^{y2} a_{i,j} = sum_{x2,y2} - sum_{x1-1,y2} - sum_{x2,y1-1} + sum_{x1-1,y1-1} 以下是二维前缀和的代码实现：
总结
前缀和是一种非常实用的算法，可以用于快速计算数组中某一段区间的和。在一维数组中，只需要预处理出前缀和数组即可；在二维数组中，需要先对每一行进行一维前缀和，然后再对每一列进行一维前缀和，得到二维前缀和数组。
3956. 截断数组
题目要求：把一个数组从中间分开两份，使得这个数组被分成三份，其中每一份都是非空的，而且要求每一份的元素的和都相等。
例：
从下标为2的地方分第一份，下标为3的地方分第二份，因此可以分成如下的三段序列：
其中每一段的和都是相等的，为3。
每一段必须是非空的，如果：
则无解，因为这个序列无法分成三份，因此输出 0
同理，如果分不出三份，使得每一份的和都相等，则也输出0
我们需要得到的是分割的方案数。
一维前缀和的思想：我们统计这个序列的前缀和，以 1 2 3 3为例：
原数组为 nums[4]={1,2,3,3} ；前缀和数组为：presum[4]={1,3,6,9}
因此我们可以发现：如果数组的总和不能被3整除，则它一定不能分成三份，此时直接输出0即可。
如果数组的总和能够被3整除，则还不一定存在方案，例如：3 3，但是它只有两份。
我们可以得出另一个结论，如果数组总和能够被3整除，并且还必须需要分成三份。
因此我们可以计算出 avg=总和的三分之一，则我们必须满足两个临界点：
- 找到一个满足 avg*2 的地方，如果找到了这个地方为i， 则后面 i到n 的和一定是avg。
- 找到一个满足 avg 的地方，如果找到了这个地方，则我们统计满足这个地方的方案数。
最后如果在 avg*2 的地方加上 avg*1 的方案数，则就是整个数组分成三份的合法方案数，因为后面的avg*3的地方就是整个数组的和，找到了这两个地方就可以确定整个数组一定是合法的。
99. 激光炸弹
题目要求：给你一个矩形区域，这个矩形区域上有几个点，每个点都具有一个值，并且给你一个R，使你在这个矩阵中所有的R*R的正方形中找到具有的值最大的一个正方形的总价值。
这道题就是二维前缀和的应用。
假设我的初始矩阵区域如图所示：
则转换为二维前缀和矩阵：
如果此时R为1，则表面上我们可以取得 2为最大值，但是其实我们的二维前缀和应该这样计算：
val=2-1-1+1=1，则答案为1，根据原二维数组我们也可知，答案为1
因此我们只需要预处理出二维数组的前缀和即可，然后根据所给的R，找到一个最大的区域，使得值最大，统计最大值即可。
需要注意的几个地方：
- 可能会出现相同的位置具有多个值，则把他们的值相加即可
- 由于没有告诉这个矩形范围是多大，因此每次我们直接枚举到题目要求的极大值即可，即5e3左右
- 从可以容纳的最小的 R*R的正方形范围开始，统计每一个R*R的值，然后统计最大值。
- 作者:Yuleo
- 链接:https://www.helloylh.com/article/b97591bd-78f5-4e2d-9bf9-a7070f4271c3
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。