前缀和

由题目引出前缀和的概念：

假设有个数组：{1, 5, 3, 2, 8}，如果有n次询问，每次询问都类似于[1,3]，意思是求下标索引在闭区间$[1, 3]$中的数的和，那么根据这样的一个数列可以得到结果为：$5+3+2=10$。

暴力枚举

如果用暴力枚举的办法来求，可写出算法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>

using namespace std;

const int N = 5;
int nums[5] = {1, 5, 3, 2, 8};

int get_sum (int l, int r) {	// 左右区间 
	int ans = 0;
	for (int i = l; i <= r; ++i) ans += nums[i];
	return ans;
}

int main () {
	cout << get_sum(1, 3) << endl;
	cout << get_sum(0, 2) << endl;
	cout << get_sum(3, 4) << endl;
}

这样的算法的时间复杂度为：$O(n*m)$ 其中n为询问次数，m为询问的区间的长度，也就是计算区间和的时间复杂度。

根据区间长度可以得到算法的时间复杂度最优为：$O(n 2)$；最差为$O(nN)$ （N为数组的长度）。

这样的算法对于只询问一次来说当然还好，但是题目中要求询问 n 次，所以我们需要一个更好的算法来优化时间复杂度。

一维前缀和

前缀和的基本思路就是：计算出到每一个数字索引位置的前面的每一个数字的和。得到一个前缀和数组。

例如：数组(nums) {1, 5, 3, 2, 8} 的前缀和数组（sums）为：{1, 6, 9, 11, 19}

这样利用前缀和数组求区间$[1, 3]$ 的值就是 ：sums[3] - sum[1] = 11 - 1 = 10

代码实现

构造前缀和数组：

原则是：

  • i == 0 ： sums[i] = nums[i]
  • else ： sums[i] = sums[i-1] + nums[i]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>

using namespace std;

const int N = 5;
int nums[5] = {1, 5, 3, 2, 8};
int sums[5];

int get_sum(int l, int r) {
	return l ? sums[r] - sums[l-1] : sums[r];
}

int main () {
	int n = sizeof(nums) / sizeof(int);
	// 构造前缀和数组 
	for (int i = 0; i < n; ++i) {
		if (i == 0) sums[i] = nums[i];
		else sums[i] = sums[i-1] + nums[i];
	}
	// 使用 
	cout << get_sum(1, 3) << endl;
	cout << get_sum(0, 2) << endl;
}
1
for (int i = 1; i <= n; ++i) sums[i] = sums[i-1] + nums[i-1];

可以简写一下得到区间和的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
#define get_sum(l, r) (l ? sums[r] - sums[l-1] : sums[r])
using namespace std;

const int N = 5;
int nums[5] = {1, 5, 3, 2, 8};
int sums[5];

int main () {
	int n = sizeof(nums) / sizeof(int);
	// 构造前缀和数组 
	for (int i = 0; i < n; ++i) {
		if (i == 0) sums[i] = nums[i];
		else sums[i] = sums[i-1] + nums[i];
	}
	// 使用 
	cout << get_sum(1, 3) << endl;
	cout << get_sum(0, 2) << endl;
}

分析这个代码的时间复杂度。

询问 n 次则询问时间为 $O(n)$

设数组长度为 N 。则构造前缀和数组的时间复杂度为 $O(N)$。

计算区间和结果的时间复杂度为：$O(1)$。

所以整体的时间复杂度为： $O(min{n, N})$

明显忧与暴力枚举的办法。

二维前缀和

有了一维前缀和的基础可以很好的得出二维前缀和。

可以根据题目要求使用两种的二维前缀和（其实两种差距不大），主要是sums[i][j]的不同含义。

sums[i][j] 表示到前 i 行的前 j 列的所有数的和

这种写法对写代码来说有一点麻烦。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <iostream>

using namespace std;

const int N = 3, M = 4;
int nums[N][M] = {
				{2, 32, 4, 2},
				{4, 8, 12, 3},
				{3, 89, 23, 11}};
int sums[N][M];

int get_sum(int r1, int l1, int r2, int l2) {
	if (r1 && l1)
		return sums[r2][l2] - sums[r1-1][l2] - sums[r2][l1-1] + sums[r1-1][l1-1];
	else 
		if (!r1&& !l1)
			return sums[r2][l2];
		else if(!r1)
			return sums[r2][l2] - sums[r2][l1-1];
		else 
			return sums[r2][l2] - sums[r1-1][l2];
}

int main () {
    sums[0][0] = nums[0][0];
	for (int i = 1; i < M; ++i) sums[0][i] = sums[0][i-1] + nums[0][i]; // 初始化第一行 
	for (int i = 1; i < N; ++i) sums[i][0] = sums[i-1][0] + nums[i][0];	// 初始化第一列 
	for (int i = 1; i < N; ++i) 
		for (int j = 1; j < M; ++j) 
			sums[i][j] = nums[i][j] + sums[i][j-1] + sums[i-1][j] - sums[i-1][j-1]; 

	cout << get_sum(1, 1, 2, 2) << endl;
	cout << get_sum(0, 0, 2, 2) << endl;
}

sums[i][j] 表示第 i 行的前 j 列的所有数的和

这样写，代码比较简洁，但是相比于上一种，在计算区间和时会更加复杂一点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream>

using namespace std;

const int N = 3, M = 4;
int nums[N][M] = {
				{2, 32, 4, 2},
				{4, 8, 12, 3},
				{3, 89, 23, 11}};
int sums[N][M];

int get_sum(int r1, int l1, int r2, int l2) {
	int ans = 0;
	for (int i = l1; i <= r2; ++i) {
		ans += l1 ? sums[i][l2] - sums[i][l1-1] : sums[i][l2];
	}
	return ans;
}

int main () {
	for (int i = 0; i < N; ++i)
		for (int j = 0; j < M; ++j)
			if (j == 0) sums[i][j] = nums[i][j];
			else sums[i][j] = sums[i][j-1] + nums[i][j];
			
	cout << get_sum(1, 1, 2, 2) << endl;
	cout << get_sum(0, 0, 2, 2) << endl;
}

差分

由题目引出差分的概念：

假设有个数组：{1, 5, 3, 2, 8}，如果有n次操作 。（每次操作类似于：$[1, 3] + 5$。即在闭区间$[1, 3]$ 中的数都加5。）求n次操作后的数组。

但是操作次数也很多，常规暴力枚举的时间复杂度一定很高。这里就不写了。

差分数组（d）为：{1, 4, -2, -1, 6}。差分数组的构造原理：

  • i == 0 : d[i] = nums[i]
  • else : d[i] = nums[i] - nums[i-1]

差分数组有一个很重要的性质：差分数组的前缀和数组刚好是原数组

一维差分

那么这道题用差分数组怎么做呢？

对操作 [l, r] + k 来说，不需要使用暴力对原数组中每一个元素进行加 k 的操作，只需要对差分数组进行

  1. d[l] + k。因为差分数组的前缀和是原数组，所以改变了d[l]的值在求原数组时，下标l之后的所有元素的值都会加k。

    相当于使下标l与下标l-1的数字的公差变化了k，但是仍然保持了l与后续的元素的公差不变，那么后续元素与l-1下标处的元素的公差都变化了k，就相当于都操作过一次了。

  2. d[r] - k。因为只对区间内的元素进行操作。所以为了不影响后续元素，需要对r后面的元素进行减小操作。

两步操作即可。其实不难，好好理解。

所以对于这种对区间操作的题。步骤就是：

  1. 求差分数组
  2. 对差分数组进行操作
  3. 对操作后的差分数组求前缀和数组，此前缀和数组就是操作后的数组。

输入格式：

第一行一个数n，表示操作n次。后面n行，每行三个数组，分别表示 l, r, k

样例输入：

3
1 3 5
0 4 -2
2 3 1

样例输出：

-1 8 7 6 6

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <iostream>

using namespace std;

const int N = 5;
int nums[N] = {1, 5, 3, 2, 8};
int d[N];

int main () {
	for (int i = 0; i < N; ++i) {	// 构造差分数组 
		if (i == 0) d[i] = nums[i];
		else d[i] = nums[i] - nums[i-1];
	} 
	int t;
	cin >> t;
	while (t--) {
		int l, r, k;
		cin >> l >> r >> k;
		// 进行操作 
		d[l] += k;
		if (r+1 < N) d[r+1] -= k;	// 注意避免下标越界 
	}
	// 得到原数组（求前缀和数列）
	for (int i = 0; i < N; ++i) {
		if (i == 0) nums[i] = d[i];
		else nums[i] = nums[i-1] + d[i];
	} 
	for (int i = 0; i < N; ++i) cout << nums[i] << " ";
}

二维差分

和前面一维差分的思想基本一致：

前面要得到差分数组，但是这里是令差分数组全部元素为0操作后的数组，然后求前缀和然后再与原数组相加。

对整体操作，即d[i][j]表示nums[i][j]及之后（i 行 j 列之后的所有元素都进行操作），适用于第一种前缀和。

样例输入：

3
0 0 2 2 2
0 2 2 2 4
0 1 2 2 -11

样例输出：

4 23 -1 2
6 -1 7 3
5 80 18 11

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <iostream>

using namespace std;

const int N = 3, M = 4;
int nums[N][M] = {
				{2, 32, 4, 2},
				{4, 8, 12, 3},
				{3, 89, 23, 11}};
int d[N][M];
int sums[N][M];

int main () {
	int t;
	cin >> t;
	while (t--) {
		int r1, l1, r2, l2, k;
		cin >> r1 >> l1 >> r2 >> l2 >> k;
		// 进行操作
		d[r1][l1] += k;
		if (r2+1 < N) d[r2+1][l1] -= k; 
		if (l2+1 < M) d[r1][r2+1] -= k;
		if (r2+1 < N && l2+1 < M) d[r2+1][l2+1] += k;	// 多减了一次
	}
	// 计算差分数组前缀和
	sums[0][0] = d[0][0];
	for (int i = 1; i < M; ++i) sums[0][i] = sums[0][i-1] + d[0][i];
	for (int i = 1; i < N; ++i) sums[i][0] = sums[i-1][0] + d[i][0];
	for (int i = 1; i < N; ++i)
		for (int j = 1; j < M; ++j)
			sums[i][j] = sums[i-1][j] + sums[i][j-1] - sums[i-1][j-1] + d[i][j];//注意加重了一次要减去
	// 操作原数组	
	for (int i = 0; i < N; ++i)
		for (int j = 0; j < M; ++j)
			nums[i][j] += sums[i][j];
	// 输出
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < M; ++j) {
			cout << nums[i][j] << " ";
		}
		cout << endl;
	}
}

单独对行操作，也就是对应上面第二种差分的思路和代码省略。