前缀和

一维前缀和

对于一个数组a[ ]，我们构造一个数组s[ ]，使得：
$s[i] = \sum_{k = 1}^i a[k]$s[i]=k=1∑i​a[k]

1. 构造前缀和

for(int i = 1; i <= n; i ++ ) {
	cin >> a[i];
	s[i] = s[i - 1] + a[i];
}

2. 求[l, r]的和

cout << s[r] - s[l - 1] << endl;

---

二维前缀和

对于一个数组a[ ][ ]，我们构造一个数组s[ ][ ]，使得：
$s[i][j] = \sum_{k_1 = 1}^i\sum_{k_2 = 1}^j a[k_1][k_2]$s[i][j]=k1​=1∑i​k2​=1∑j​a[k1​][k2​]

这样可能不是很直观，我们用一个图形来表示：

图中绿色部分即为s[i][j]

1. 构造前缀和

由于构造前缀和是一个从上到下，从左到右的一个过程。所以对于s[i][j]来说，s[i - 1][j]和s[i][j - 1]已经被构造过了，我们可以利用已有结果去构造s[i][j]：

for(int i = 1; i <= n; i ++)
	for(int j = 1; j <= m; j ++ ) {
		cin >> a[i][j];
		//  s[i - 1][j - 1]被加了两次，所以要减去一次
		s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];
	}

2. 求子矩阵的和

给定(x1, y1), (x2, y2)，求该子矩阵的和。其中(x1, y1)为矩阵左上角坐标，(x2, y2)为矩阵右下角坐标。

由图我们可以看出：

// 红色部分被减了两次，所以要加上一次
cout << s[x2][y2] - s[x2, y1 - 1] - s[x1 - 1, y2] + s[x1 - 1][y1 - 1] << endl;