【算法】手把手学会前缀和

目录

前缀和

前缀和的好处

🎵前缀和算法可以理解为是一种以空间换时间的方式，通过建立一个新的数组来存储从头到当前位置的数据的总和。

公式的推导

初始化数组

 🎵前缀和数组的初始化就是将前 i 个数存在一个新的数组之中，这里用 a 表示原数组，s 表示前缀和数组。在计算时，由于当前 i 位置的上一位表示的就是1 ~ i-1的前缀和，于是我们便可以在此基础上加上原数组上的值(a[i])就是当前位置的前缀和了。

🎵于是初始化的公式便优化成s[i] = s[i-1] + a[i] 。

🎵也正是这个原因前缀和数组的下标必须从1开始，且默认s[0] = 0 才能保证s[1]就是a[1]的本身。如此循环一趟便可完成前缀和数组的初始化。

区间和

🎵求区间和才是特意建立前缀和数组的目的，要求区间和的时候若我们每次都暴力地直接进行区间遍历，随着区间长度和计算次数的增加，会出现非常多次的重复计算。

🎵若提前用前缀和数组记录下来就可以将每次计算的时间复杂度优化到 O(1) ，极大地优化了代码的效率。那前缀和数组怎么求区间和呢，让我们现在来看看。

 🎵我们设左边界为 l ，右边界为 r ，根据性质便可以得到如下等式，若要求数组的一段区间和，只需要在前缀和数组中用 r 的值减去 l-1 的值，此行为即表示将左边界之前的值删去，那剩下的便是我们要求的区间和了。

例题：前缀和

🎵 传送门：AcWing 795. 前缀和

🎵题目要求使用前缀和数组进行区间数的求和，就跟我们上面推导的公式一样，只需要初始化完前缀和数组后，根据公式输出结果就能够完成题目要求。更多细节我们通过代码来看看。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>

using namespace std;

const int N = 100010;
int n,m;
int s[N],a[N];

int main() 
{
	scanf("%d%d",&n,&m);
	for(int i = 1;i<=n;i++)
	{
		scanf("%d",&a[i]);     //读入原数组
		s[i] = s[i-1] + a[i];  //初始化前缀和数组
	}
	while(m--)  //  m组数据
	{
		int l,r;
		scanf("%d%d",&l,&r);
		printf("%d\n",s[r]-s[l-1]);  //根据边界求区间和
	}
	return 0;
}

二维前缀和

🎵二维前缀和便是在一维前缀和的基础上，拓展了一个维度，在(i, j)位置表达的便是从(1,1)开始一直到(i, j)这个范围内所有的值的和。注意: 这里画的图都是以(1,1)为起点进行表示的。

推导公式

初始化

🎵这里从图示出发，我们也很容易观察到，若我们想要对其进行初始化只需要，用上部分矩阵加上左部分矩阵，但这个过程中中间部分被算了两次所以需要扣掉一次，最后再补上当前位置的值即可，即s[i,j] = a[i, j] + s[i, j-1] + s[i-1, j] – s[i-1, j-1]。

求区间和

🎵假设求的是 (x1,y1) 到 (x2,y2) 的区间和，我们可以看到目标区间就是紫色的矩阵，就像求一维前缀和那样，我们只要保留目标区间，其他多余的部分都要删除，现在我们要删除掉的就是目标矩阵上方和左边的两个矩阵，即 s[x1-1, y2] 和 s[x2, y1-1] ，很明显两者有一个重复的空间s[x1-1, y1-1]（数据再大一点就不仅仅只是一格而已），而连续扣掉两个矩阵后这个重复的空间便会被减去两遍，于是我们需要将其加一遍回来。

🎵即 s[x1y1,x2y2] = s[x2, y2] – s[x2, y1-1] – s[x1-1, y2] + s[x1-1, y1-1]

 例题: 子矩阵的和

🎵 传送门: AcWing 796. 子矩阵的和

🎵 通过上面的讲解，这道题目就变得相当简单了，根据题目要求建立二维前缀和数组，之后根据公式求区间和，便可完成任务要求。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>

using namespace std;

const int N = 1010;
int a[N][N], s[N][N];
int n, m, q;

int main()
{
	scanf("%d%d%d", &n, &m, &q);
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			scanf("%d", &a[i][j]);     //原数组输入
		}
	}

	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];  //初始化二维前缀和数组
		}
	}
	while (q--)
	{
		int x1, y1, x2, y2;
		scanf("%d%d%d%d", &x1, &y1, &x2, &y2);  //接收区间
		printf("%d\n", s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1]); //根据区间和的公式求区间和
	}
	return 0;
}

🎵 好了这次前缀和数组的入门讲解到这里就结束了，如果对你有用的话还请留下你的三连加关注。关注博主，共同进步！！！