定义：

C++前缀和是一种常用的算法，用于解决求解区间和问题。前缀和数组是一个长度为n的数组，其中第i个元素代表原始数组从下标0到下标i的元素之和。通过预先计算前缀和数组，可以在O(1)的时间复杂度内求解任意区间的和。

前缀和数组	值
s[1]	a[1]
s[2]	a[1] + a[2]
s[3]	a[1] + a[2] + a[3]
s[4]	a[1] + a[2] + a[3] + a[4]
…	…
s[i]	s[i – 1] +a[i]

前缀和的计算过程

1. 首先初始化前缀和数组 s[0] = 0, 表示数组 a 的前 0 个元素的和为 0
2. 然后从 1 开始遍历整个数组 a，逐个计算每个位置的前缀和。即 s[i] = s[i – 1] + a[i];
3. 最终 s[i] 数组中存放了 数组 a 的前缀和，s[i] 表示数组 a 的前 i 个元素的和

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

数组 s 叫做前缀和数组，用来存储原数组前 i 项的和

功能：方便计算区间和

区间和

给定任意一个区间 [a,b]，求这个区间内的所有元素之和

下标	1	2	3	4	5	6
原数组 a[]	3	-6	5	4	3	9
前缀和数组 s[i]	3	-3	2	6	9	18

如何计算区间 [3,5] 之间的和？

[3,5] 这段区间和：a[3] + a[4] + a[5]

s[5]： a[1] + a[2] + a[3] + a[4] + a[5]

s[2]：a[1] + a[2]

所以，[3,5] 这段区间的区间和= s[5] – s[2]

由此可以推断出：

对于任意区间 [L,R] 的区间和= s[R] – s[L – 1]

一般适用的题目类型

1. 快速计算数组区间和：通过预先计算数组的前缀和，可以在O(1)的时间复杂度内快速计算任意区间的和，而不需要每次都重新遍历计算。
2. 解决子数组和为特定值的问题：通过计算前缀和，在一维数组中可以快速找到和为特定值的子数组。
3. 解决数组中连续子数组的最大和问题：通过计算前缀和，可以优化求解连续子数组的最大和问题，使得时间复杂度可以达到O(n)。
4. 解决求解区间和的问题：通过利用前缀和的特性，可以在较快的时间内解决求解多个区间和的问题。
5. 判断两个子数组是否具有相同的和：通过计算不同位置的前缀和，可以快速判断两个子数组是否具有相同的和，用于一些比较问题中。

总的来说，前缀和在解决数组相关的问题时，具有非常重要的作用，可以优化计算效率，减少时间复杂度

一维数组前缀和

#include<iostream>
using namespace std;
 
int a[110], s[110];
 
//下标 1  2  3  4  5
//a[]  2  4  6  8  10
//ps[] 2  6  12 20 30
int main() {
	//n个元素，m次查询，每次查询[l,r]的元素之和
	int n; cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		//前i项和=前i-1项和+第i项
		s[i] = s[i - 1] + a[i];//O(n)
	}
 
	int m; cin >> m;
	while (m--) {
		int l, r; cin >> l >> r;
		int sum = 0;
		//for (int i = l; i <= r; i++) sum += a[i];//O(n)
		sum = s[r] - s[l - 1];//o(1)
		cout << sum << endl;
	}
 
	return 0;
}

二维数组前缀和

根据上述拆分逻辑，用前缀和符号替换 “区域”：

区域 1 = S[i−1][j]（上侧矩形和）；

区域 2 = S[i][j−1]（左侧矩形和）；

区域 3 = S[i−1][j−1]（重叠区域和）；

区域 4 = A[i][j]（当前元素）。

因此得到二维前缀和的核心递推公式：

S[i][j]=S[i−1][j]+S[i][j−1]−S[i−1][j−1]+A[i][j]

#include<iostream>
using namespace std;
 
int a[110][110], s[110][110];
 
int main() {
	//n个元素，m次查询，每次查询lx,ly和rx,ry围成的矩阵和
	int n, m; cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> a[i][j];
			//1,1点到i,j点围成矩阵和-二维前缀和
			s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];
		}
	}
 
	int k; cin >> k;
	while (k--) {
		//求lx,ly和rx,ry围成的矩阵和
		int lx, ly, rx, ry; cin >> lx >> ly >> rx >> ry;
		int sum = 0;
		//for()
		// for()
		//二维前缀和求矩阵和
		sum = s[rx][ry] - s[lx - 1][ry] - s[rx][ly - 1] + s[lx - 1][ly - 1];//O(1)
		cout << sum << endl;
	}
 
	return 0;
}