蓝桥备赛（24）算法篇【前缀和】

一、前缀和

前缀和与差分的核心思想是   预处理 ， 可以再暴力枚举的过程中 ， 快速给出查询结果 ， 从而优化时间复杂度。

是经典的用空间替换时间的做法 。

二、 一维前缀和

登录—专业IT笔试面试备考平台_牛客网

注意： 使用前缀和数组时候 ， 下标必须从 1 开始计数 ， 这样真的超级方便、简洁，规避了很多越界的情况 ， 如果你下标从0开始 ， 需要使用if 判断 ~

在来简述以下方法：

1.创建前缀和数组： f[i] = f[i − 1] + a[i] 

 2.查询 [l, r] 区间和： f[r] − f[l − 1]

#include <iostream>
using namespace std;

typedef long long LL;
const int N = 1e5 + 10;
LL a[N],f[N];//f[N]前缀和数组
int n,q; 

int main()
{
	cin >> n >> q;
	for(int i = 1;i<=n;i++)cin >> a[i];
	
	//处理前缀和数组
	for(int i = 1 ;i<=n;i++)
	{
		f[i] = f[i-1] + a[i];
	} 
	//处理q次询问
	while(q--)
	{
		int l,r;
		cin >> l >> r;
		cout << f[r] - f[l-1] << endl;
	 } 
	return 0;
}

三、最大字段和

P1115 最大子段和 - 洛谷

#include <iostream>
using namespace std;

typedef long long LL;
const int N = 2e5 + 10; 
int n;
LL f[N];//前缀和数组 
int main()
{
	
	cin >> n;
	for(int i = 1;i<=n;i++)
	{
		LL x;
		cin >> x;
		f[i] = f[i-1] + x;
	}
	
	//初始化为负的无穷大 
	//因为最小字段和也可能是负数 
	LL ret = -1e20;
	LL prevmin = 0;
	for(int i = 1;i<=n;i++)
	{
		ret = max(ret,f[i]-prevmin);
		prevmin = min(prevmin,f[i]);
	}
	cout << ret << endl;
	return 0;
}

四、二维前缀和

登录—专业IT笔试面试备考平台_牛客网

#include <iostream>
using namespace std;

typedef long long LL;
const int N = 1010;
int n,m,q;
LL f[N][N];

int main()
{
	cin >> n >> m >> q;
	for(int i = 1;i<=n;i++)
	{
		for(int j = 1;j<=m;j++)
		{
			LL x;cin >> x;
			f[i][j] = f[i-1][j] + f[i][j-1] - f[i-1][j-1] + x;
		}
	}
	//处理q次查询
	 while(q--)
	 {
	 	int x1,y1,x2,y2;
	 	cin >> x1 >> y1 >> x2 >> y2;
	 	cout << f[x2][y2] - f[x1-1][y2] - f[x2][y1-1]+f[x1-1][y1-1] << endl;
	 }
	return 0;
}

五、激光炸弹

P2280 [HNOI2003] 激光炸弹 - 洛谷

#include <iostream>
using namespace std;

const int N = 5010;
int n,m;
int a[N][N];
int f[N][N];//前缀和矩阵 

int main()
{
	cin >> n >> m;
	while(n--)
	{
		int x,y,v;
		cin >> x >> y >> v;
		x++,y++;//下标从1开始计数
		a[x][y] += v;//同一个位置，有可能存在多个目标
	}
	n = 5001;
	//预处理前缀和矩阵 
	for(int i = 1;i<=n;i++)
	{
		for(int j = 1;j<=n;j++)
		{
			f[i][j] = f[i-1][j]+f[i][j-1]-f[i-1][j-1]+a[i][j];
		}
	}
	//枚举所有边长为m的正方形
	int ret = 0;
	m = min(m,n);//如果炸弹威力大,可以把整个区域全部都摧毁 
	for(int x2 = m;x2 <= n ; x2++)
	{
		for(int y2 = m ; y2 <= n;y2++)
		{
			int x1 = x2 - m +1;
			int y1 = y2 - m +1;
			ret = max(ret,f[x2][y2] - f[x1-1][y2] - f[x2][y1-1] + f[x1-1][y1-1]);
		}	
	} 
	cout <<ret << endl;
	return 0;
 }