前缀和 | OI笔记

前缀和与差分算法

---

前缀和算法好处：能实现O(1)时间复杂度内计算和
注意:
为处理边界问题，统一从下标1开始读入，且a[0] = 0、
使得求区间之和有统一的公式S[i] - S[j - 1]

一维前缀和

const int N = 100000;
int ans[N + 10];

int main()
{
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= n; i ++)
		cin >> ans[i];
	
	for (int i = 1; i <= n; i ++)
		ans[i] += ans[i - 1];
	// 求出所有位置的前缀和
	
	while (m --)
	{
		int a, b;
		cin >> a >> b;
		cout << ans[b] - ans[a - 1] << endl;
	}
	// 输出所需的前缀和
	
	return 0;
}

---

二维前缀和

表示在当前格子[i,j]左上方所有数之和

基本公式：

计算特定区间内一段方格的和：
s[x2, y2] - s[x1 - 1, y2] - s[x2, y1 - 1] + s[x1 - 1, y1 - 1]

计算s[i][j]：
s[i,j] = s[i - 1, j] + s[i，j - 1] - s[i - 1, j - 1] + a[i, j]

const int N = 1000;
int a[N + 10][N + 10];
int main()
{
	int n, m, q;
	cin >> n >> m >> q;
	for (int i = 1; i <= n; i ++)
	// 注意：下标从1开始
		for (int j = 1; j <= m; j ++)
		{
			cin >> a[i][j];
			a[i][j] += a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1];
		}
		// 输入并计算前缀和
	
	while (q --)
	{
		int x1, y1, x2, y2;
		cin >> x1 >> y1 >> x2 >> y2;
		cout << a[x2][y2] - a[x2][y1 - 1] - a[x1 - 1][y2] + a[x1 - 1][y1 - 1] << endl;
	}
	return 0;
}

#差分

差分是前缀和的逆运算

一维差分

应用举例：
将A数组的[l, r]区间全部加上一个常数c，如果使用暴力计算的时间复杂度为O(n)，而如果使用差分算法，只需要对A数组的差分数组B进行如下处理：B[l] += c ， B[r + 1] -= c，而此时的时间复杂度为O(1)

对于A数组，构造一个数组B使得B成为A数组的差分数组：

基本思想：
将A数组中的第i个元素视为在A数组的[i, i]区间插入数值为A[i]的数

void(int l, int r, int c)
{
	b[l] += c;
	b[l + 1] -= c;
}

---

二维差分

二维矩阵的差分计算，如果在某一区间[x1, x1][x2, y2]增加一个常量c，那么只需要

b[x1][y1] += c;
b[x2 + 1][y1] -= c;
b[x1][y2 + 1] -= c;
b[x2 + 1][y2 + 1] += c;

初始化和一维差分矩阵的插入类似，只需要视为在[i, j][i, j]插入一个值为c的数