【AcWing】前缀和与差分（一维 + 二维）

前缀和与差分（一维 + 二维）

这一部分内容来自于AcWing基础算法课的前缀和与差分部分，主要包含四道前缀和与差分的例题。

前缀和可以在$O(1)$的时间复杂度内进行区间求和，而差分可以在$O(1)$的时间复杂度内完成区间内值的修改。

一维前缀和

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int maxn = 1e5 + 5;
int n, m;
int q[maxn] = {0};
int p[maxn] = {0};

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> n >> m;
    for(int i=1;i<=n;i++){
        cin >> q[i];
        p[i] = p[i-1] + q[i];   // 在输入q的过程中直接对前缀和p进行维护
    }
    // 1 2 3 4 5
    // 1 3 6 10 15
    while(m--){
        int l, r;
        cin >> l >> r;
        cout << p[r] - p[l-1] << endl;
    }
    return 0;
}

二维前缀和

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int maxn = 1e3 + 5;
int n, m, q;
int a[maxn][maxn] = {0};
int b[maxn][maxn] = {0};

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m >> q;
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=m; j++){
            cin >> a[i][j];
            b[i][j] = b[i-1][j] + b[i][j-1] - b[i-1][j-1] + a[i][j];
        }
    }
    
    while(q--){
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        cout << b[x2][y2] - b[x1-1][y2] - b[x2][y1-1] + b[x1-1][y1-1] << endl;
    }
    return 0;
}

一维差分

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int maxn = 1e5 + 5;
int n, m;
int q[maxn] = {0}, p[maxn] = {0};

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for(int i=1;i<=n;i++){
        cin >> q[i];
        p[i] = q[i] - q[i-1];
    }
    // 1 2 3 4 5 -> 1 2 13 14 5
    // 1 1 1 1 1 -> 1 1 11 1 -9
    
    while(m--) {
        int l, r, k;
        cin >> l >> r >> k;
        p[l] += k;
        p[r+1] -= k;
    }
    
    for(int i=1;i<=n;i++){
        p[i] += p[i-1];
        cout << p[i] << " ";
    }
    return 0;
}

二维差分

其中，二维差分最难理解，在本科阶段的程序设计竞赛当中，我的印象里是肯定遇到过二维差分的模板题的，并且那道题应该是被算作了一道较难的题目，因此对二维差分进行完全理解是很有意义的。

二维差分矩阵的作用是快速地对二维矩阵从$(x_1,y_1)$到$(x_2,y_2)$的值进行修改，使这个区间内的值加上$c$。显然如果直接使用暴力求解的话，时间复杂度将来到$O(n^2)$，而如果在处理输入的同时维护一个二维差分矩阵，则可以将时间复杂度降低到$O(1)$。

这里理解差分的一个关键点是，原始的输入矩阵是其差分矩阵的前缀和矩阵，如何理解这句话？我们可以先看一个一维的例子：

假定原始矩阵为：

1 2 3 4 5 6 7 8 9 10

其差分矩阵必然是：

1 1 1 1 1 1 1 1 1 1

显然对上述矩阵求前缀和即可恢复出原始矩阵。再看一个更复杂的例子：

假定原始矩阵为：

3 6 9 12 4 -7

其差分矩阵为：

3 3 3 3 -8 -11

不难看出原始矩阵仍然是差分矩阵的前缀和矩阵。

下面来看二维的情况，首先需要理清楚的是，二维矩阵的前缀和代表的是某个位置$(x,y)$和$(1,1)$之间矩阵元素值之和。因此如果原始矩阵为：

1 2 3 4
5 6 7 8
9 0 1 2
3 4 5 6

差分矩阵的构造仅考虑其相邻的元素，假定当前位置的下标为$(i,j)$，差分矩阵记为$b$，原矩阵记为$A$，那么该位置的差分值就是：$b[i][j]=a[i][j]-a[i][j-1]-a[i-1][j]+a[i-1][j-1]$。

上述矩阵的差分矩阵如下，可以自行验证上述矩阵是下述差分矩阵的前缀和矩阵。

 1  1  1  1
 4  0  0  0
 4 -10 0  0
-6  10 0  0 

以$0$为起始下标，如果想要修改$(1,1)$到$(2,2)$，使它们都加上$1$，在原始矩阵上直接进行修改的时间复杂度是$O(n^2)$，直接使用暴力法对相应下标进行遍历即可。但我们可以直接在差分矩阵上进行修改，从而将时间复杂度降低到$O(1)$。

修改后的矩阵变为：

1 2 3 4
5 7 8 8
9 1 2 2
3 4 5 6

其差分矩阵为：

 1  1  1  1
 4  1  0 -1
 4 -10 0  0
-6  9  0  1

根据差分矩阵的变化，可以推导出二维差分的区间修改公式：

假定要对二维区间$a$进行修改，使得$(x_1,y_1)$和$(x_2,y_2)$之间的数加上$c$，那么可以在$O(1)$内对差分矩阵$b$的以下位置进行如下修改：

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

在最后输出时，直接对上述矩阵$b$求二维前缀和即可：

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int maxn = 1e3 + 5;
int n, m ,q;

int b[maxn][maxn] = {0};

void insert(int x1, int y1, int x2, int y2, int c) { // 将二维差分的维护抽象为insert函数
    b[x1][y1] += c;
    b[x1][y2+1] -= c;
    b[x2+1][y1] -= c;
    b[x2+1][y2+1] += c;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m >> q;
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=m; j++){
            int x;
            cin >> x;
            insert(i, j, i, j, x);	// 注意这里是一个trick, 相当于直接对全0矩阵进行二分差分的维护
            // 直接对维护过后的二维矩阵求前缀和即可得到最开始的输入矩阵, 这样避免了在最开始输入矩阵之
            // 后重复对矩阵求一次二维差分的过程
        }
    }
    
    while(q--) {
        int x1, y1, x2, y2, x;
        cin >> x1 >> y1 >> x2 >> y2 >> x;
        insert(x1, y1, x2, y2, x);
    }
    
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            b[i][j] += b[i-1][j] + b[i][j-1] - b[i-1][j-1]; // 对二维矩阵求前缀和得到最终结果
            cout << b[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}