【0基础学算法】前缀和 (超详细讲解+私人笔记+源码）

目录

什么是前缀和

我们为什么要去学习前缀和

前缀和实现

如何求s[i] 

S[i]的作用 

模板

一维前缀和

二维前缀和

题目

第一题

第二题

---

哈喽大家好，很长时间忘记更新咱们的学算法系列文章了，今天我们终于迎来了我们零基础学算法的第四期内容，那就是前缀和，前缀和其实算是一个偏数学概念，所以我相信你只要了解了这方面知识，就肯定可以去写出正确的代码的，下面我们也废话少说直接进入我们的讲解阶段。

什么是前缀和

假定给我们一个数组，前缀和就是该元素前所以元素和。也就是如果我们设定一个数组s为前缀和数组，那么s[3]就是我们原数组前三个元素之和，这就是我们的前缀和。

我们为什么要去学习前缀和

有很多人疑惑，我们为什么要学习前缀和，在这里我们之所以学习前缀和的原因是因为其可以有效的减少时间复杂度。

如果我们要求一段区间的和，那么我们用普通数组要从第一个加到最后一个循环一边，但是如果我们知道该数组前缀和之后，我们就只需要去让其末元素前缀和减去初元素前的前缀和就可以了。

就比如我们求下标3-10的数组和，那么我们使用前缀和时就只需要去让是s[10]-s[2] 就可以了。

 这样就可以有效的降低我们去计算时的复杂度，这就是为什么我们要去学习前缀和。所以我们下面就要去了解一下前缀和的实现过程。

前缀和实现

这里我们主要是要解决两个问题：

1.如何求s[i] ?

2.S[i]的作用 ?

如何求s[i] 

我们在这里将用递推的方法去具体的去求s[i] ，我们在前面已经了解了前缀和的定义，那么我们从头开始求前缀和，之后的前缀和就是其前一个前缀和加上当前元素了。

也就是：

S[i] = S[i-1] + a[i] ;

这样我们循环下来，或者说是我们在输入数组的时候就可以顺便的求出我们的前缀和数组。

当然在这里我们统一的将下表设置为从1开始，具体是要考虑到我们的边界问题，也就是S[1]的求法问题，为了保证我们循环的统一性，我们要将S[0]设置为0，所以我们索性就将下标从1开始设置起，这样也有利于我们后面的初始化。

S[i]的作用 

我们前面也提到过，S[i]的作用就是可以快速求出一段区间数的合。

也可以表示为：

S[r] - S[l-1] = a[l] + ... + a[r] ;

利用这个特性可以求一个区间的区间和 。

模板

在这里我们将差分的模板分成两类：也就是一维前缀和和二位前缀和。

一维前缀和

一维前缀和也就是我们前面举例子的时候所提到的，也就是针对一维数组所作的前缀和，那么我们通过前面的了解肯定理解了一维前缀和，那么我们就直接放出一维前缀和的代码模板：

S[i] = a[1] + a[2] + ... a[i]
a[l] + ... + a[r] = S[r] - S[l - 1]

这就是我们学习一维前缀和的核心代码串。 

 

 

二维前缀和

对于二维前缀和我们在举例子的时候没有举这个方面的例子,主要是因为二维前置和要相对于一维前缀和更复杂一点，对应的运算也要复杂一点，所以二维前缀和在这里我们为其讲解。

首先我们给出一个二维数组：

如果我们相求（4，4)的前缀和的话，我们就需要求出这块部分的数值。

 

 我们想要求这块面积需要怎么求呢？

公式是：    s[i][j] += s[i-1][j] + s[i][j-1] - s[i-1][j-1] 

那我们来看一下：

s[4][3]：

s[3][4]:

 

 这时我们会发现，如果我们这两个相加的话，我们会相加重叠一部分，那么这个时候我们就需要将中间那一部分减去。

 这里我们不难看出，重叠的相加部分就是我们的s[i-1][j-1] ;

这里可能会有人提出疑问，是不是还有一块没加上，但是为什么公式中体现的是s[i][j]，这里我们对于二维数组初始化时，不需要建立新的数组，我们只需要使用原数组，将原数组填入其中即可，所以这里的s[i][j]就是当前那一格的大小，在我们更新后，他才成为了起二维前缀和。

这里我们了解了二维数组的初始化之后就要去计算一段区间的二维前缀和，其计算方法与初始化相似，公式：S = S[x2, y2] - S[x1 - 1, y2] - S[x2, y1 - 1] + S[x1 - 1, y1 - 1] 。

这里就不做具体的讲解了，如果还不太清楚的话，可以按上面的方法去试着推理一下就可以了，其原理是相同的，到代码实现的时候这两个我们也是可以使用一个模板的，因为我们前面的初始化，是相同点，也就是点相同是所围成矩阵值，那就是那一格的值，到后面我们就是两个不同的点所围成的值，就是传入两个不同的点就可以了。

 

代码模板：

S[i, j] = 第i行j列格子左上部分所有元素的和
以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵的和为：
S[x2, y2] - S[x1 - 1, y2] - S[x2, y1 - 1] + S[x1 - 1, y1 - 1]

到这里我们也就学会了前缀和，那么我们下面来写几个题目来了解一下吧。 

题目

第一题

输入一个长度为 n 的整数序列。

接下来再输入 m 个询问，每个询问输入一对 l,r。

对于每个询问，输出原序列中从第 l 个数到第 r 个数的和。

输入格式

第一行包含两个整数 n 和 m。

第二行包含 n 个整数，表示整数数列。

接下来 m 行，每行包含两个整数 l 和 r，表示一个询问的区间范围。

输出格式

共 m 行，每行输出一个询问的结果。

数据范围

1≤l≤r≤n
1≤n,m≤100000
−1000≤数列中元素的值≤1000

输入样例：

5 3
2 1 3 6 4
1 2
1 3
2 4

输出样例：

3
6
10

讲解

这道题目就是单纯的考察了我们一维前缀和的使用，我们在前面已经讲过了计算区间和的时候使用前缀和数组的公式。

那么首先我们要对前缀和数组进行初始化，具体初始化方式就是从前往后逐个初始化：
 

for(int i=1; i<=n; i++)	s[i] = s[i-1] + a[i] ;

之后，我们再利用前缀和数组去计算我们的区间和：

 

for(int i=1; i<=m; i++)
	{
		cin >> l >> r ;
		
		cout << s[r]-s[l-1] << endl ;        //输出区间和
	}

我们要注意在初始化的时候下标和边界，注意到这两点这个题也就会变的不那么容易出错了。 

AC

#include
 
using namespace std ;
 
const int N = 100010 ;
 
int n, m ;
int l, r ;
int a[N] , s[N] ;
 
 
int main()
{
	cin >> n >> m ;
	for(int i=1; i<=n; i++)	cin >> a[i] ;
	
	for(int i=1; i<=n; i++)	s[i] = s[i-1] + a[i] ;    //计算前缀和
	
	for(int i=1; i<=m; i++)
	{
		cin >> l >> r ;
		
		cout << s[r]-s[l-1] << endl ;        //输出区间和
	}
	
	return 0 ;
} 

第二题

输入一个 n 行 m 列的整数矩阵，再输入 q 个询问，每个询问包含四个整数 x1,y1,x2,y2表示一个子矩阵的左上角坐标和右下角坐标。

对于每个询问输出子矩阵中所有数的和。

输入格式

第一行包含三个整数 n，m，q。

接下来 n 行，每行包含 m 个整数，表示整数矩阵。

接下来 q 行，每行包含四个整数 x1,y1,x2,y2，表示一组询问。

输出格式

共 q 行，每行输出一个询问的结果。

数据范围

1≤n,m≤1000,
1≤q≤200000,
1≤x1≤x2≤n,
1≤y1≤y2≤m,
−1000≤矩阵内元素的值≤1000

输入样例：

3 4 3
1 7 2 4
3 6 2 8
2 1 2 3
1 1 2 2
2 1 3 4
1 3 3 4

输出样例：

17
27
21

讲解

这个题目就正好可以考察我们二维前缀和的学习情况，那么我们已经在前面讲解了二维前缀和的计算方式，那么我们在这里就将其的实现细化一下。

首先我们要初始化一下二位前缀和 

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] ;
		}
	}

在这里我们还是要注意到边界问题，也就是0的问题，因为我们在计算S[1]的时候要用到S[0]所以我们在这里就要让S[0] = 0 ；

之后我们在这里只用到了一个数组，也就是我们数组在更新前是二维数组单个元素，更细后的就编变成了其前缀和元素了。

之后我们要去计算其区间和，具体方法在前面也讲到过，代码实现就如下：

 

cin >> x1 >> y1 >> x2 >> y2 ;
		cout << s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1] << endl ;    //计算和

 

AC

#include
 
using namespace std ;
 
const int N = 1010 ;
 
int n, m , q ;
int x1, x2, y1, y2 ;
int s[N][N] ;
 
int main()
{
	cin >> n >> m >> q ;
	
	for(int i=1; i<=n; i++)
	{
		for(int j=1; j<=m; j++)
		{
			cin >> s[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] ;
		}
	}
	
	while(q--)
	{
		cin >> x1 >> y1 >> x2 >> y2 ;
		cout << s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1] << endl ;    //计算和
	}
	
	return 0 ;
}

好啦，到这里我们今天的讲解内容也就结束了，也希望你可以学会这个知识，加油我们每天进步一点，到时候回头看来，将是一大步飞跃。