文章目录
- 前缀和
- 二维前缀和
- 总结
- 3956. 截断数组
- 99. 激光炸弹
前缀和
前缀和是一种常见的算法，用于快速计算数组中某一段区间的和。前缀和的思想就是预处理出数组中前缀和，然后用后缀和减去前缀和，即可快速计算区间和。
以一维数组为例，设 表示数组中第
个元素的值，
表示数组中前
个元素的和，即：
则对于区间
的和可以表示为：
这里需要注意的是，我们需要在原数组的前面插入一个值为
的元素，这样才能计算出
，也就是前
vector<int> a; // 原数组
vector<int> sum(a.size() + 1, 0); // 前缀和数组
// 计算前缀和
for (int i = 1; i <= a.size(); i++) {
sum[i] = sum[i-1] + a[i-1];
}
// 计算区间和
int l = 3, r = 7;
int ans = sum[r] - sum[l-1]; //[3,7]的区间和二维前缀和
对于二维数组，我们可以先对每一行进行一维前缀和，然后对每一列进行一维前缀和，即可得到二维前缀和数组。 设 表示二维数组中第
行第
列的元素值，
表示以
为右下角的矩阵的元素和，则有：
则对于矩阵
的元素和可以表示为：
vector<vector<int>> a; // 原数组
vector<vector<int>> sum(a.size() + 1, vector<int>(a[0].size() + 1, 0)); // 二维前缀和数组
//前缀和的预处理
for (int i=1;i<=a.size();i++){
for (int j=1;j<=a[0].size();j++){
sum[i][j]+=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];
}
}
// 计算矩阵的元素和
int x1 = 2, y1 = 3, x2 = 5, y2 = 7;
int ans = sum[x2][y2] - sum[x1-1][y2] - sum[x2][y1-1] + sum[x1-1][y1-1];总结
前缀和是一种非常实用的算法，可以用于快速计算数组中某一段区间的和。在一维数组中，只需要预处理出前缀和数组即可；在二维数组中，需要先对每一行进行一维前缀和，然后再对每一列进行一维前缀和，得到二维前缀和数组。
3956. 截断数组
题目要求：把一个数组从中间分开两份，使得这个数组被分成三份，其中每一份都是非空的，而且要求每一份的元素的和都相等。
例：
4
1 2 3 3从下标为2的地方分第一份，下标为3的地方分第二份，因此可以分成如下的三段序列：
1 2, 3 , 3其中每一段的和都是相等的，为3。
每一段必须是非空的，如果：
2
0 0则无解，因为这个序列无法分成三份，因此输出 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的地方就是整个数组的和，找到了这两个地方就可以确定整个数组一定是合法的。
#include <iostream>
#include <algorithm>
using namespace std;
#define int long long
const int N=1e5+10;
int nums[N],presum[N];
int n;
signed main(){
cin>>n;
int sum=0;
for (int i=1;i<=n;i++){
cin>>nums[i];
presum[i]=nums[i]+presum[i-1];
sum+=nums[i];
}
if (sum%3!=0){
//一定不能分成三份
cout<<0;
}
else{
int avg=sum/3;
int js=0;
int ans=0;
for (int i=1;i<n;i++){
//一定要留给第三份一个元素的空间，所以不能取到n
if (presum[i]==avg*2){
ans+=js;
}
if (presum[i]==avg){
++js;
}
}
cout<<ans<<endl;
}
return 0;
}99. 激光炸弹
题目要求：给你一个矩形区域，这个矩形区域上有几个点，每个点都具有一个值，并且给你一个R，使你在这个矩阵中所有的R*R的正方形中找到具有的值最大的一个正方形的总价值。
这道题就是二维前缀和的应用。
假设我的初始矩阵区域如图所示：
1 0
0 1则转换为二维前缀和矩阵：
1 1
1 2如果此时R为1，则表面上我们可以取得 2为最大值，但是其实我们的二维前缀和应该这样计算：
val=sum[i][j]-sum[i-1][j]-sum[i][j-1]+sum[i][j]val=2-1-1+1=1，则答案为1，根据原二维数组我们也可知，答案为1
因此我们只需要预处理出二维数组的前缀和即可，然后根据所给的R，找到一个最大的区域，使得值最大，统计最大值即可。
需要注意的几个地方：
- 可能会出现相同的位置具有多个值，则把他们的值相加即可
- 由于没有告诉这个矩形范围是多大，因此每次我们直接枚举到题目要求的极大值即可，即5e3左右
- 从可以容纳的最小的 R*R的正方形范围开始，统计每一个R*R的值，然后统计最大值。
#include <iostream>
#include <algorithm>
using namespace std;
const int N=5010;
int nums[N+10][N+10];
int n,r;
int main(){
cin>>n>>r;
//r可能会出现一个大值：1e9，但是只需要到N即可
r=min(r,N);
for (int i=1;i<=n;i++){
int x,y,w;
cin>>x>>y>>w;
nums[x+1][y+1]+=w;//可能出现相同的位置，值相加
}
//预处理前缀和
for (int i=1;i<=N;i++){
for (int j=1;j<=N;j++){
nums[i][j]+=nums[i-1][j]+nums[i][j-1]-nums[i-1][j-1];
}
}
//求出每一个R*R的正方形做具有的最大值
int ans=0;
for (int i=r;i<=N;i++){
for (int j=r;j<=N;j++){
ans=max(ans,nums[i][j]-nums[i-r][j]-nums[i][j-r]+nums[i-r][j-r]);
}
}
cout<<ans;
return 0;
}