算法日记——前缀和、差分

文章目录

• • 洛谷 B3612 求区间和
  • 洛谷 P1387 最大正方形
  • 洛谷 P3397 地毯

洛谷 B3612 求区间和

题目链接：洛谷 B3612 求区间和
思路： 一维前缀和的模板题。所谓前缀和，就是对原数组前i个元素求和，这个值作为新元素放在下标i的位置。
代码如下：

#include <iostream>
using namespace std;
const int N = 1e5 + 5;
int a[N], sum[N];
int main()
{
	int n, m;
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
		sum[i] += sum[i - 1] + a[i];
	}
	cin >> m;
	while (m--)
	{
		int l, r;
		cin >> l >> r;
		cout << sum[r] - sum[l - 1] << endl;
	}
	return 0;
}

• 时间复杂度$O(n)$
• 空间复杂度$O(n)$

洛谷 P1387 最大正方形

题目链接： 洛谷 P1387 最大正方形
思路： 本题有两种方法，一种是利用二位前缀和，另一种是利用动态规划。
代码如下：
（前缀和）

#include <iostream>
using namespace std;
int n, m;
const int N = 105;
int a[N][N], s[N][N]; 
int ans;//保存最大边长
int main()
{
	cin >> n >> m;
	for(int i = 1; i <= n; i ++ )
		for (int j = 1; j <= m; j++)
		{
			cin >> a[i][j];
			s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];
		}
	//枚举起点和边长
	for(int i = 1; i <= n; i ++ )
		for(int j = 1; j <= m; j ++ )
			for (int l = 1; l <= min(n, m); l ++ )
			{
				int x = i + l - 1, y = j + l - 1;//正方形右下角坐标
				if (x > n || y > m || s[x][y] - s[x][j - 1] - s[i - 1][y] + s[i - 1][j - 1] != l * l) {
					break;
				}
				if (ans < l) ans = l;
			}
	cout << ans << endl;
	return 0;
}

• 时间复杂度$O(mnl)$
• 空间复杂度$O(n^2)$

（动态规划）

#include <iostream>
#include<algorithm>
using namespace std;
const int N = 105;
int a[N][N], f[N][N]; //f[i][j]表示以节点i, j为右下角，可构成的最大正方形的边长。
int ans;
int main()
{
	int n, m;
	cin >> n >> m;

	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
		{
			cin >> a[i][j];
			if (a[i][j] == 1) {
				f[i][j] = min(f[i - 1][j - 1], min(f[i - 1][j], f[i][j - 1])) + 1;
			}
			ans = max(ans, f[i][j]);
		}
	cout << ans << endl;
	return 0;
}

• 时间复杂度$O(n^2)$
• 空间复杂度$O(n^2)$

洛谷 P3397 地毯

题目链接： 洛谷 P3397 地毯
思路： 算是二维差分的模板题吧。所谓差分也就是前缀和的逆运算，也就是说，我们对差分数组求前缀和后得到的数组就是原数组。
代码如下：

#include <iostream>
#include<algorithm>
using namespace std;
const int N = 1005;
int n, m;
int b[N][N], s[N][N];//b为差分数组，s为原数组（对差分数组求前缀和）

int main()
{
	cin >> n >> m;
	while (m--)
	{
		int x1, y1, x2, y2;
		cin >> x1 >> y1 >> x2 >> y2;
		b[x1][y1] += 1;
		b[x1][y2 + 1] -= 1;
		b[x2 + 1][y1] -= 1;
		b[x2 + 1][y2 + 1] += 1;
	}
	for(int i = 1; i <= n; i ++ )
		for (int j = 1; j <= n; j++)
		{
			s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + b[i][j];
		}
	for (int i = 1; i <= n; i ++ ) {
		for (int j = 1; j <= n; j ++ )
			cout << s[i][j] << " ";
		cout << endl;
	}
	return 0;
}

• 时间复杂度$O(mn+n^2)$
• 空间复杂度$O(n^2)$

总结： 对于前缀和、差分来说，一般比赛时不会直接作为考点，而是融合在其他类型题目中：比如利用前缀和、差分来对初始数组进行操作，从而方便我们解决问题。

最后，如果文章有错误，请在评论区或私信指出，让我们共同进步！