新生培训之前缀和与差分 ----一维前缀和篇

用户11956880

发布于 2025-12-18 18:22:07

860

前缀和与差分这两个算是算法入门学的第一个东西了，也是算法竞赛中经常用到的技巧，挺重要的

前者是用于快速求区间和，后者用于高效进行区间修改。我们在这先去了解前缀和

前缀和

前缀和可以简单理解为「数列的前 𝑛

项的和」，是一种重要的预处理方式。

这里我们记录前缀和数组为prefix ，原数组是arr

这里说一下prefix与arr之间的关系

prefix[0] = arr[0] prefix[1] = arr[0] + arr[1] prefix[2] = arr[0] + arr[1] + arr[2] ... prefix[i] = arr[0] + arr[1] + ... + arr[i]

换成数也就是 arr=[1 1 1 1 1 1]

prefix[0]=1;

prefix[1]=1+1

prefix[2]=1+1+1

...

我们可以得出

递推公式

prefix[i] = prefix[i-1] + arr[i] (当 i ≥ 1 时) prefix[0] = arr[0] (当 i = 0 时)

上面说了前缀和就是数组从初到n的前n项和，那如果我想得到一个区间内的数组的和呢

所以通过前缀和我们能快速得到一个区间内的和

求区间和

sum(l, r) = prefix[r] - prefix[l-1] sum(0, r) = prefix[r]

就这样，通过 𝑂(𝑛)

时间预处理，能够将单次查询区间和的复杂度降低到 𝑂(1)

。

下面这个代码可以看一下

#include<bits/stdc++.h>
using namespace std;
int prefix[10000];//定义在全局变量，就能保证prefix[0]=0,所以这样就不用担心边界 
int arr[1000];
int n;
//得到区间和 
int get_sum(int l,int r){
	return prefix[r]-prefix[l-1];
}
//得到前缀和数组 
void get_prefix(){
	for(int i=1;i<=n;i++){
		prefix[i]=prefix[i-1]+arr[i];
	}
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>arr[i];
	}
	int t=10;
	while(t--){
		int a,b;
		cin>>a>>b;
		get_prefix();
		cout<<get_sum(a,b);	
	}

}

差不多就这些了，后面拿点题练习一下

练习

P3131 [USACO16JAN] Subsequences Summing to Sevens S

P3131 [USACO16JAN] Subsequences Summing to Sevens S - 洛谷

题目描述

Farmer John 的 N 头奶牛站成一排，这是它们时不时会做的事情。每头奶牛都有一个独特的整数 ID 编号，以便 Farmer John 能够区分它们。Farmer John 希望为一组连续的奶牛拍照，但由于童年时与数字 1…6 相关的创伤事件，他只希望拍摄一组奶牛，如果它们的 ID 加起来是 7 的倍数。

请帮助 Farmer John 确定他可以拍摄的最大奶牛组的大小。

输入格式

输入的第一行包含 N（1≤N≤50,000）。接下来的 N 行每行包含一头奶牛的整数 ID（所有 ID 都在 0…1,000,000 范围内）。

输出格式

请输出 ID 之和为 7 的倍数的最大连续奶牛组中的奶牛数量。如果不存在这样的组，则输出 0。

显示翻译

题意翻译

输入输出样例

输入 #1复制

输出 #1复制

说明/提示

在这个例子中，5+1+6+2+14=28。

思路：

暴力直接写肯定是过不了的，数据范围有点大，我们可以用减法同余原理也就是（a%mod-b%mod）= (a-b)%mod ，用到我们这题就是下面这个图

那我们可以用一个大小为7的数组就可以去存一下每一段模7之后的值，然后看之后好不好出现重复，出现了那我们就可以得到像上图一样的长度

先给一下暴力写（我水一下字数）

#include<bits/stdc++.h>
using namespace std;
long long prefix[50020];
int arr[50020];
int n;
int main(){
	ios::sync_with_stdio(false);
	    cin.tie(nullptr);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>arr[i];
		prefix[i]=prefix[i-1]+arr[i];
	}
	int ans=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=i;j++){
			int sum=prefix[i]-prefix[j-1];
			if(sum%7==0){
				ans=max(ans,i-j+1);
			}
		}
	} 
	cout<<ans;
}

下面是正确的做法

#include<bits/stdc++.h>
using namespace std;
int arr[50020];
int n,mod7[7];
long long prefix;
int main(){
	ios::sync_with_stdio(false);
	    cin.tie(nullptr);
	cin>>n;
	int max_len=0;
	memset(mod7,-1,sizeof(mod7));
	mod7[0]=0;//我们从1开始算，位置为0的前缀和mod7也就是0了，因为没数 
	for(int i=1;i<=n;i++){
		cin>>arr[i];
		(prefix+=arr[i])%=7;//这也算是用来加法同余原理
		 
		if(mod7[prefix]==-1){//如果没出现过就等于这里的位置 
			mod7[prefix]=i;
		}
		else{
			max_len=max(i-mod7[prefix],max_len);
		}
	}
	cout<<max_len;

}

P4440 [COCI 2017/2018 #3] Programiranje

P4440 [COCI 2017/2018 #3] Programiranje - 洛谷

题目描述

Little Leticija 正在准备编程考试。虽然她已经解决了很多任务，但还有一个任务尚未解决，于是她向你寻求帮助。

有一个单词 S 和 Q 次询问。在每次询问中，给出正整数 A、B、C 和 D。假设单词 X 由单词 S 中位置 A 和 B 及其之间的字母组成，而单词 Y 由位置 C 和 D 及其之间的字母组成。您需要回答是否能以某种方式重新排列单词 Y 中的字母得到单词 X。

输入格式

第一行输入包含单词 S（1≤∣S∣≤50000）。∣S∣ 表示单词 S 中的字符数。S 完全由英文小写字母组成。

第二行输入包含正整数 Q（1≤Q≤50000）。以下 Q 行中的每一行包含四个整数 A、B、C 和 D（1≤A≤B≤∣S∣ 且 1≤C≤D≤∣S∣）。

输出格式

对于每次询问，如果可能，输出DA（即克罗地亚语的“是”），如果不可能，则输出NE（克语的“否”）。

显示翻译

题意翻译

输入输出样例

输入 #1复制

kileanimal
2
2 2 7 7
1 4 6 7

输出 #1复制

DA
NE

输入 #2复制

abababba
2
3 5 1 3
1 2 7 8

输出 #2复制

DA
DA

输入 #3复制

vodevovode
2
5 8 3 6
2 5 3 6

输出 #3复制

NE
DA

说明/提示

对于 50% 的测试点，有 1≤∣S∣≤1000 且 1≤Q≤1000。

对于 100% 的测试点，有 1≤∣S∣≤50000，1≤Q≤50000，1≤A≤B≤∣S∣ 且 1≤C≤D≤∣S∣。

样例 #3 的解释：在第一次询问中，X=vovo，Y=devo。在第二次询问中，X=odev，Y=

思路

看这个题，这个我们要求的前缀和当然和上题的不一样了，这个我们的和是字母数量的和，我们定义一个数组prefix[i][j]，j就是0到25分别代表每个字母，i就是这个字母的长度，这个数组的意思就是到达长度i时候j字母的数量大小，那我们预处理一下每个数据的前缀和，然后后面判断就行了

这个可能比上面那个麻烦点但思路都大差不差

#include<bits/stdc++.h>
using namespace std;
string s; 
int prefix[50020][50];
int main(){
	ios::sync_with_stdio(false);
	    cin.tie(nullptr);
	    cin>>s;
	    //这里循环还是从1开始比较好，要不然后面还要特判 
	    for(int i=1;i<=(int)s.size();i++){
			for(int j=0;j<26;j++){
				prefix[i][j]=prefix[i-1][j];
			}
			prefix[i][s[i-1]-'a']++;
		}
	    int q;
	    cin>>q;
	    while(q--){
			int a,b,c,d;
			int flag=1;
			cin>>a>>b>>c>>d;
		//	a--,b--,c--,d--; 
			for(int i=0;i<26;i++){
				//数量有一个不一样就说明字母数量不同直接break就行了 
				if(prefix[b][i]-prefix[a-1][i]!=prefix[d][i]-prefix[c-1][i]){
					flag=0;
					break;
				}
			}
			if(flag==1){
				cout<<"DA"<<endl;
			}
			else{
				cout<<"NE"<<endl;
			}
		}

}

P6180 [USACO15DEC] Breed Counting S

P6180 [USACO15DEC] Breed Counting S - 洛谷

题目描述

Farmer John 的 N 头奶牛，从左到右编号为 1…N，排成一队。

所有牛都可以分为三个品种，每头牛都有一个品种编号（只能为 1,2,3 中的一个）。FJ 有 Q 个询问，每个询问希望求出某个区间内每个品种奶牛的数量。

输入格式

第一行两个整数 N,Q（1≤N,Q≤105）。

接下来 N 行，每行一个整数，第 i 个整数代表第 i 头奶牛的品种编号。

接下来 Q 行，每行两个整数 a,b，表示第 i 次查询的范围是 [a,b]。

输出格式

对于每个查询，输出三个整数，分别是指定区间内品种 1 的奶牛数量，品种 2 的奶牛数量，品种 3 的奶牛数量。

输入输出样例

输入 #1复制

输出 #1复制

3 2 1
1 0 0
2 0 1

思路：

也没啥思路，就和上题一样解法，没直接看代码

#include<bits/stdc++.h>
using namespace std;
int n,q;
int prefix[500020][4]; 
int main(){
	ios::sync_with_stdio(false);
	    cin.tie(nullptr);
	    cin>>n>>q;
		for(int i=1;i<=n;i++){
			int id;
			cin>>id;
			for(int j=1;j<=3;j++){
				prefix[i][j]=prefix[i-1][j];
			}
			prefix[i][id]++;
		} 
		while(q--){
			int a,b;
			cin>>a>>b;
			for(int i=1;i<=3;i++){
				cout<<prefix[b][i]-prefix[a-1][i]<<' ';
			}
			cout<<endl;
		}
}

P6625 [省选联考 2020 B 卷] 卡牌游戏

P6625 [省选联考 2020 B 卷] 卡牌游戏 - 洛谷

题目描述

轩轩某天想到了一个卡牌游戏，游戏规则如下：

初始时轩轩的手中有自左向右排成一排的 n 张卡牌，每张卡牌上有一个整数分值。
接下来，轩轩每次可以选取卡牌序列最左边的连续若干张卡牌（至少 2 张），将它们替换为一张新卡牌。新卡牌将插入到序列的最左端，它的分值为本次操作中被替换掉的卡牌的分值之和。
初始时轩轩总分为 0，每执行一次卡牌替换操作，新卡牌的分值将加到总分中。当序列长度为 1 时游戏结束，轩轩也可以在任意时刻结束游戏。

现在给出序列中各个卡牌的分值，请你来帮助轩轩计算他能够获得的最高总分是多少？

输入格式

第一行一个正整数 n，代表卡牌的数目。

接下来一行 n 个以空格分隔的整数，第 i 个数字 ai 代表自左向右第 i 张卡牌的分值。

输出格式

仅一行一个整数表示答案。

输入输出样例

输入 #1复制

3
2 -1 2

输出 #1复制

输入 #2复制

7
-4 3 0 7 -3 -5 -3

输出 #2复制

说明/提示

样例解释 1

最优策略为，首先选择最左侧的两张卡牌，总分增加 2+(−1)=1。此时轩轩选择的两张卡牌被替换为一张分值为 1 的卡牌，且被放入序列最左侧，此时自左向右卡牌的分值为 1 和 2。

接下来选择当前序列中所有卡牌，总分增加 1+2=3，总分为 4。此时轩轩选择的两张卡牌被替换为一张分值为 3 的卡牌，且被放入序列最左侧，此时序列中只有一张分值为 3 的卡牌，游戏结束。

样例解释 2

最优策略为，首先选择最左侧的四张卡牌，总分增加 (−4)+3+0+7=6。此时轩轩选择的四张卡牌被替换为一张分值为 6 的卡牌，且被放入序列最左侧，此时自左向右卡牌的分值为 6,−3,−5,−3。

再选择最左侧的两张卡牌，总分增加 6+(−3)=3，总分为 9。此时轩轩选择的两张卡牌被替换为一张分值为 3 的卡牌，且被放入序列最左侧，此时自左向右卡牌的分值为 3,−5,−3。

此时无论如何操作均无法使总分继续增大，轩轩选择结束游戏。

数据范围与约定

测试点 1∼6 满足：1≤n≤16,∣ai∣≤100。

测试点 7∼12 满足：1≤n≤103,∣ai∣≤100。

测试点 13∼20 满足：1≤n≤105,∣ai∣≤105。

思路：

这题就是让你让你把前缀和给加起来就行，我们只加前缀和大于0的如果后面一直小于0，咱不加就行，题上也说了可以提前停止。这个也不难直接看代码

#include<bits/stdc++.h>
using namespace std;
int n,arr[100020]; 
long long ans,sum;
int main(){
	ios::sync_with_stdio(false);
	    cin.tie(nullptr);
	cin>>n;
	for(int i=0;i<n;i++){
	    int sc;
	    cin>>sc;
	    sum+=sc;
	    if(i>0){
			ans+=sum>0?sum:0;
		}
		
	}
	cout<<ans;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-10-03，如有侵权请联系 cloudcommunity@tencent.com 删除

游戏