前缀和与差分

原理介绍

一维前缀和

前缀和是一种预处理技巧，可以 O(1) 时间查询任意区间的和。

定义原数组 a[1..n]，前缀和数组 s[i] = a[1] + a[2] + ... + a[i]。
查询区间 [l, r] 的和：sum(l, r) = s[r] - s[l-1]。

一维差分

差分是前缀和的逆运算，可以 O(1) 时间对区间进行批量加减，最后通过一次前缀和还原结果数组。

定义差分数组 d，使得 a[i] = d[1] + d[2] + ... + d[i]。
若要对区间 [l, r] 每个元素加 x，只需：

1
2
d[l] += x;
d[r+1] -= x;

二维前缀和

在矩阵中快速求子矩阵和。

定义 s[i][j] 为原矩阵 a 从 (1,1) 到 (i,j) 的子矩阵元素和。
递推公式:

1
s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + a[i][j]

查询以 (x1, y1) 为左上角，(x2, y2) 为右下角的子矩阵和:

1
sum = s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1]

二维差分

与一维差分类似，用于对子矩阵进行批量加减，最后通过二维前缀和还原矩阵。
二维差分的构造:

1
2
3
4
diff[x1][y1]+= v;
diff[x2+1][y1]-= v;
diff[x1][y2+1]-= v;
diff[x2+1][y2+1]+= v;

二维差分数组求前缀和:

1
diff[i][j] = diff[i][j] + diff[i - 1][j] + diff[i][j - 1] - diff[i - 1][j - 1];

最后附上代码:

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
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, m, x1, y1, x2, y2;
    cin >> n >> m;

    // 差分矩阵，多开两行两列防止越界
    vector<vector<int>> diff(n + 2, vector<int>(n + 2, 0));

    // 处理 m 次子矩阵增加操作
    for (int i = 0; i < m; i++) {
        cin >> x1 >> y1 >> x2 >> y2;
        diff[x1][y1] += 1;
        diff[x2 + 1][y1] -= 1;
        diff[x1][y2 + 1] -= 1;
        diff[x2 + 1][y2 + 1] += 1;
    }

    // 二维前缀和还原矩阵
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            diff[i][j] = diff[i][j] + diff[i - 1][j] + diff[i][j - 1] - diff[i - 1][j - 1];
            cout << diff[i][j] << ' ';
        }
        cout << endl;
    }
    return 0;
}