C++知识点总结(10)：差分、二维前缀和

1. 二维前缀和

1.1 真题

对于图中的二维数组，图中10对应的二位前缀和是多少？

1	2	3	4
5	6	7	8
9	10	11	12

【答案】 33
【解析】 从左上角，一直到要求的数字为止，画一个矩形，其圈住的数字之和为对应的二维前缀和。

1.2 计算公式

依据真题上表，已知前面所有的前缀和，求12的前缀和。

下标	1	2	3	4
1	11	23	36	410
2	56	614	724	836
3	915	1033	1154	12??

$$S[3][4]=S[3][3]+S[2][4]?S[2][3]+a[3][4]$$
其中，$S[][]$表示前缀和数组，$a[][]$表示前缀和数组。
上述的公式其实就相当于：

目标前缀和 = 左侧前缀和 + 上方前缀和 - 左上前缀和 + 本身

根据上面的文字公式，我们得出了公式：
$$S[i][j]=S[i][j?1]+S[i?1][j]?S[i?1][j?1]+a[i][j]$$
拓展一下区间和公式：
$$sum=s[x2][y2]?s[x1?1][y2]?s[x2][y1?1]+s[x1?1][y1?1]$$

1.3 练习

【题目描述】

在一个充满科技的未来世界，人们使用一种特殊的数字矩阵来进行信息传输。这种数字矩阵的行数和列数分别是$x$和$y$，而矩阵中的每个数字都代表着一种特殊的信息。
一天，年轻的科学家小李在研究这种数字矩阵时，发现了一个神奇的现象。他发现，通过对这个矩阵进行一种特殊的计算，可以得到一个新的矩阵，这个新矩阵可以揭示出原矩阵隐藏的信息。
计算规则如为：新矩阵的每个位置的值为原矩阵从左上角到自己所在位置的所有元素的总和
小李非常兴奋，他想要立刻进行这种计算，但是他发现这个计算过程非常复杂，他需要你的帮助。
你能帮助小李完成这个计算吗？

【输入描述】

第一行为两个数字$x$和$y$，分别表示矩阵的行数和列数。之后$x$行，每行$y$个用空格分开的整数，表示矩阵中的数。

【输出描述】

$x$行，每行$y$个数，用空格间隔，表示新矩阵。

【样例1】

输入

2 3
1 2 3
5 6 7

输出

1 3 6
6 14 24

【提示】

$x<=1000$，$y<=100$，每个数$a[x][y]$的大小不超过$1000$。

【参考代码】

#include <iostream>
using namespace std;

int main()
{
	// 准备数据 
	int x, y; 
	int a[1005][105] = {};
	int s[1005][105] = {};
	
	// 输入与存储 
	cin >> x >> y; 
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			cin >> a[i][j];
			s[i][j] = s[i][j-1] + s[i-1][j] - s[i-1][j-1] + a[i][j]; // 二维前缀和公式 
		}
	}
	
	// 输出 
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			cout << s[i][j] << " ";
		}
		cout << endl;
	}
	return 0;
}

二、差分

【题目描述】

给定一个一维数组，请你计算出它的一维差分数组。

【输入描述】

第一行为一个数$n$，表示数组的长度。第二行有$n$个用空格分开的数，表示数组中的数。

【输出描述】

在一行内输出$n$个用空格分开的数，表示一维差分数列。

【样例1】

输入

5
1 3 6 10 15

输出

1 2 3 4 5

【提示】

$n$不超过$100$，每个数的大小不超过$1000$。

【参考答案】

#include <iostream>
using namespace std;

int main()
{
	// 准备数据 
	int n;
	int a[105] = {};
	int dfr[105] = {};
	
	// 输入数据
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
		dfr[i] = a[i] - a[i-1];
		cout << dfr[i] << " ";
	}
	return 0;
}

关于更多真题，请订阅C++知识点总结此合集。我会发送真题的~