一篇带你速通前缀和算法（C/C++）

前缀和是一种常见的算法计算技巧，通常用于处理数组或序列的连续子区间求和问题。它可以帮助我们在 O(1) 的时间内计算出指定子区间的和，而不需要每次都遍历整个子区间。前缀和一般用于预处理当中，具有高效率的特点。

摆烂小白敲代码

2063人浏览 · 2024-09-04 11:57:04

摆烂小白敲代码 · 2024-09-04 11:57:04 发布

个人主页：摆烂小白敲代码

创作领域：算法、C/C++

持续更新算法领域的文章，让博主在您的算法之路上祝您一臂之力

欢迎各位大佬莅临我的博客，您的关注、点赞、收藏、评论是我持续创作最大的动力

前缀和是一种常见的算法计算技巧，通常用于处理数组或序列的连续子区间求和问题。它可以帮助我们在 O(1) 的时间内计算出指定子区间的和，而不需要每次都遍历整个子区间。前缀和一般用于预处理当中，具有高效率的特点。

算法思想：

一维前缀和：

前缀和由名字可知，前面的数相加为和，前缀和是算法最基础的，也是非常好理解的，其实与数学符号Σ（求和符号）的意思是一模一样的。下面举一个例子我们有原数组a=[3,5,1,6,4]，前缀和数组为sum，每一个sum[i]，都是所有下标为i前面的（包括i）a[0~i]相加，例如sum[2]=3+5+1=9。为了更简单的写递推式，前面i-1项我们可以用之前求出的前缀和sum[i-1]代替（sum[i-1]比sum[i]早一步求出），所以就有了sum[i]=sum[i-1]+a[i]的前缀和递推式。

二维前缀和：

前面我们讲述的是一维前缀和，其数组为一维的，其模型可以抽象为线性的。那么有些时候需要我们使用二维前缀和，当题目出现矩阵时，说明就涉及到了二维前缀和，其模型可以抽象为矩阵，只要一维会了，二维前缀和自然也就很简单了。我们设presum[i][j]为（1，1）点到（i，j）点的子矩阵和（1<=x<=i,1<=y<=j），二维前缀和定义可如下：

那么如何求解子矩阵的和呢？看下面这张图，要求（x1,y1）到（x2,y2）这个子矩阵的和，那么前缀和presum[x][y]是由起点（1,1）到（x,y)的值，如何转换成起点为（x1,y1）呢，很简单，如图求红色的矩阵的值，=整个大矩阵-黄色矩阵-绿色矩阵-蓝色矩阵。那么就可以理解为presum[x2][y2]=A+B+C+D，A矩阵的起点是（1,1），所以黄色矩阵A也可以表示为presum[x1][y1]，那么我们将黄色矩阵A分别于B、C进行合并，这样起点就是（1,1）了，可以用前缀和表示了。那么红色矩阵D=presum[x2][y2]-(A+B)-(A+C)+A，我们将它转化为前缀和的形式，注意不能取到顶点，那么D=presum[x2][y2]-presum[x1-1][y2]-presum[x2][y1-1]+presum[x1-1][y1-1]

算法实现：

由于前缀和一般用于预处理过程，一般直接在输入的循环内一块处理。下面给大家展示前缀和的C++程序，前面为一维前缀和、后面为二维前缀和处理过程。

#include<iostream>
using namespace std;
const int N=1005;
int n;
int a[N],sum[N];
int b[N][N],presum[N][N];
int main(){
	//一维前缀和
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		sum[i]=sum[i-1]+a[i];
	}
	//sum[i]为前i项的和
	//若求[l,r]区间和，可以利用sum[r]-sum[l-1]
	//例如：[2,5]这个区间和等于sum[5]-sum[1]=a[1]+a[2]+a[3]+a[4]+a[5]-a[1]=Σa(2~5)
	//下面可进行其他操作
	
	//二维前缀和
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cin>>b[i][j];
			presum[i][j]=presum[i][j-1]+presum[i-1][j]-presum[i-1][j-1]+b[i][j];//递推关系实现
		}
	}
	//presum[i][j]为横坐标1——i,1——j子矩阵之和
	//若求（x1,y1）到（x2,y2）这个矩阵的值
	//sum=presum[x2][y2]-presum[x2][y1-1]-presum[x1-1][y2]+presum[x1-1][y1-1]
	return 0;
}

算法应用：

前缀和是一种在数组或序列中快速计算任意子区间和的技术。通过预先计算每个位置的前缀和，可以迅速得出任意两个位置之间的元素和，而不需要重新遍历整个区间。前缀和在许多算法问题中都有应用，包括但不限于：

快速区间查询：快速计算数组中任意两个索引之间的和。
动态规划：在需要计算状态转移时，前缀和可以简化计算过程。
滑动窗口问题：在需要维护一个固定大小的窗口内元素和的场景中，前缀和可以快速更新窗口的和。
股票交易问题：计算股票在特定时间段内的收益。
区间更新问题：在需要快速更新区间内元素并计算新区间和的场景中。

算法例题：

由于前缀和算法思想以及实现非常简单，在题目中一般是不会直接考察，都是会跟其他算法结合起来一块考察，由于此篇为了让大家学习前缀和，这里选几道题目比较具有代表性的题目给大家讲解以下，涉及到的其他算法不会太难，请大家放心食用。

洛谷 P1115 最大子段和

题目描述

给出一个长度为 n 的序列 a，选出其中连续且非空的一段使得这段和最大。

输入格式

第一行是一个整数，表示序列的长度 n。

第二行有 n 个整数，第 i 个整数表示序列的第 i 个数字 ai。

输出格式

输出一行一个整数表示答案。

输入

7
2 -4 3 -1 2 -4 3

输出

说明/提示

选取 [3,5]子段 {3,−1,2}，其和为 4。

数据规模与约定

对于 40% 的数据，保证 n≤2×10^3。
对于 100% 的数据，保证 1≤n≤2×10^5，−10^4≤ai≤10^4。

解题思路：

这道题看上去就是考一个一维前缀和，可是事实如此吗？那肯定不是的，但是还是有一点前缀和的思想在里面的，如果我们采用之前上面所说的前缀和，求[l,r]区间最大子段和，我们要枚举l，再去枚举r，这样就需要两个for循环时间复杂度就达到了O（n^2），n最大2e5+5,肯定会TLE的，我们不妨把前缀和定义为presum[i]表示前1~i项最大子段和，不让它考虑前面所有的项，只让它考虑最大子段和的那几项，这样问题就迎刃而解了，实际上这道题还是主要是动态规划的思想。

AC代码：

#include<iostream>
using namespace std;
const int N=2e5+5;
int n;
int a[N],presum[N];//presum[i]表示前1~i项最大子段和
int maxx=-0x3f3f3f;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		presum[i]=max(a[i],presum[i-1]+a[i]);//要么自己要么就与前面的构成子段
		maxx=max(maxx,presum[i]);
	}
	cout<<maxx<<endl;
	return 0;
}

洛谷 P1114 “非常男女”计划

题目描述

近来，初一年的 XXX 小朋友致力于研究班上同学的配对问题（别想太多，仅是舞伴），通过各种推理和实验，他掌握了大量的实战经验。例如，据他观察，身高相近的人似乎比较合得来。

万圣节来临之际，XXX 准备在学校策划一次大型的 “非常男女” 配对活动。对于这次活动的参与者，XXX 有自己独特的选择方式。他希望能选择男女人数相等且身高都很接近的一些人。这种选择方式实现起来很简单。他让学校的所有人按照身高排成一排，然后从中选出连续的若干个人，使得这些人中男女人数相等。为了使活动更热闹，XXX 当然希望他能选出的人越多越好。请编写程序告诉他，他最多可以选出多少人来。

输入格式

第一行有一个正整数 n (1≤n≤10^5)，代表学校的人数。

第二行有 n 个用空格隔开的数，这些数只能是 0 或 1，其中，0 代表是一个女生 1 代表是一个男生。

输出格式

输出一个非负整数。这个数表示在输入数据中最长的一段男女人数相等的子区间的长度。

如果不存在男女人数相等的子区间，请输出 0。

输入

9
0 1 0 0 0 1 1 0 0

输出

解题思路：

这道题看上去无非是求解男生前缀和跟女生前缀和，然后去枚举区间，在枚举区间时，我们采用区间DP的思想，先去枚举区间长度再去枚举区间起点，这样只要找到第一个满足条件的就是最优解，时间复杂度最坏的情况下为O(n^2)，很可惜，这个题测试样例有一个样例刚好卡在了这个点上去了，所以这个样例会TLE，前缀和这样解会TLE一个点，当然这也是一个很好的思路。最优的解法为引入相对差的概念。即a[i]表示第i个位置男生人数-女生人数的差值。那么差值相等的两个位置之间的人数是满足男女相等的。从此统计l[a[i]]和r[a[i]]。特别要注意的是a[0]=0 统计的时候要把0的位置当做差为0的起点。

代码实现：

#include<iostream>
using namespace std;
const int N=1e5+5;
int n;
int a[N],boy[N],girl[N];
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		girl[i]=girl[i-1]+(a[i]==0?1:0);//女生前缀和
		boy[i]=boy[i-1]+(a[i]==1?1:0);//男生前缀和
	}
	for(int i=n;i>=0;i--){//枚举区间长度
		if(i%2==0){//能够组成一对，必然为偶数
			for(int j=1;j<=n-i+1;j++){//枚举区间起点
				if(girl[i+j-1]-girl[j-1]==boy[i+j-1]-boy[j-1]){//满足人数相同
					cout<<i<<endl;//由于区间长度由大到小枚举，第一次满足的一定是最大的
					return 0;
				}
			}
		}
	}
	return 0;
}

AC代码：

#include <bits/stdc++.h>
using namespace std;
int l[200010],r[200010],sum1,sum0,ans,n;
int main()
{
    cin>>n;
    for (int i=1;i<=n;i++){
        int x; cin>>x;
        sum1+=(x==1), sum0+=(x==0);
        int t=sum0-sum1+n;
        if (!l[t]&&t!=n) l[t]=i; else r[t]=i;
    }
    for (int i=0;i<=2*n;i++) ans=max(ans,r[i]-l[i]);
    cout<<ans<<endl;
    return 0;
}