一维前缀和笔记

一、导入：

1、暴力求解：求数组的第x个数字到第y个数字的和

//代码一
#include<bits/stdc++.h>
using namespace std;
int a[1000010];
int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	int x,y,s=0;
	cin>>x>>y;
	for(int i=x;i<=y;i++){
		s+=a[i];
	}
	cout<<s;
	return 0;
}

以上代码的数据范围说明：1<=n<=1000000,所有求和不超出int范围。

2、多次暴力求解：求数组的第x个数字到第y个数字的和

//代码二
#include<bits/stdc++.h>
using namespace std;
int a[1000010];
int main(){
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	while(m--){
		int x,y,s=0;
		cin>>x>>y;
		for(int i=x;i<=y;i++){
			s+=a[i];
		}
		cout<<s<<endl;
	}
	return 0;
}

以上代码的数据范围说明：1<=n,m<=1000000,所有求和不超出int范围。

题目时间限制为1s，不想提交代码超时，一个代码最大的循环次数（时间复杂度）应该控制在10的8次方以内！

请算一算代码二的时间复杂度 n * m=1000000*1000000=10的12次方

远远超过10的8次方,提交代码只能TLE

一维前缀和可以巧妙地解决TLE的问题

二、一维前缀和

前提：a数组是存储输入的数据，b数组是前缀和数组

1、理解一维前缀和数组b[i]的含义

b[i]是a数组前i个数字的和

2、根据含义构建一维前缀和数组b

数组a

4	2	1	3	6	5

一维前缀和数组b

4	6	7	10	16	21

构建方法：b[i=b[i-1]+a[i];

3、使用一维前缀和数组b

1、快速求解：求数组的第x个数字到第y个数字的和

快速求解：int s=b[y]-b[x-1];

快速求解代码：求数组的第x个数字到第y个数字的和

#include<bits/stdc++.h>
using namespace std;
int a[1000010],b[1000010];
int main(){
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		b[i]=b[i-1]+a[i];
	}
	while(m--){
		int x,y;
		cin>>x>>y;
		int s=b[y]-b[x-1];
		cout<<s<<endl;
	}
	return 0;
}

易错点：

问：一维前缀和数组要开多大？ 答：和存储数据的a数组一样大。

问：为什么不是b[y]-b[x]? 答：因为b[x]包含了a[x]这个数字。

三、例题

例题1

https://www.yuanmabc.cn/p/P5306 思考：一维前缀和数组b[i]的含义？

步骤：先构建前缀和数组，再使用前缀和数组

回到题目，按照步骤先尝试自己写代码

参考代码：

例题2

https://www.yuanmabc.cn/p/P5378

只有自己独立写出正确代码才是真正地理解哦！

四、练习题

https://www.yuanmabc.cn/p/P1995

五、为下个知识点准备

https://www.yuanmabc.cn/p/P5307