acwing算法基础之基础算法--前缀和算法

1 知识点

前缀后下标尽量从1开始，当然不从1开始也是ok的。
$a_1,a_2,a_3,...,a_n$
$S_1,S_2,S_3,...S_n$
$S_i$：原数组nums中前$i$个元素的和，注意边界情况$S_0=0$。
前缀和的作用，$O(1)$时间复杂度下求取原数组中任一区间和[l,r]。

二维前缀和
初始化（类似于递推公式）：
$S(i,j)=S(i-1,j)+S(i,j-1)-S(i-1,j-1)+nums[i][j]$
计算任一矩形面积：
$(x_1,y_1)$、$(x_2,y_2)$
$S(x_2,y_2)-S(x_1-1,y_2)-S(x_2,y_1-1)+S(x_1-1,y_1-1)$

2 模板

//一维前缀和
//原数组nums，它第1个元素是无效的，即nums[0]是无效的
//前缀和数组s
//原数组中[l,r]区间之和为:s[r]-s[l-1]。注意此处的l和r均不考虑无效元素nums[0]，也即下标从1开始。
int n = nums.size();
vector<int> s(n);
s[0] = 0;
for (int i = 1; i < n; ++i) {
	s[i] = s[i-1] + nums[i];
}

//求区间[l,r]元素之和
s[r] - s[l-1]
1
2
3
4
5
6
7
8
9
10
11
12
13

//二维前缀和
//原数组nums,其中第0行和第0列是无效值
int n = nums.size(), m = nums[0].size();
vector<vector<int>> s(n, vector<int>(m, 0));
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] + nums[i][j];
	}
}

//(x1,y1) (x2,y2) 注意此处下标从1开始。
//求子矩阵的和
s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1]
1
2
3
4
5
6
7
8
9
10
11
12
13