差分矩阵

个人理解谈一谈差分的核心思想。
和一维差分类似。
一维差分是：b[l] += c; b[r + 1] -=c;
到了二维，由于是r+1 而不是r,
b[x1][y1] += c;
b[x2 + 1][y1] -= c;
b[x1][y2 + 1] -=c;
b[x2 + 1][y2 + 1] += c;

b[x2 + 1][y1] -= c;
b[x1][y2 + 1] -=c;
这两行代码执行了之后，所有包含(x2 + 1, y1),(x1, y2 + 1)，之后取前缀和的时候，这两个位置的点都会减c。
同理，肯定会有重复的地方，这个地方减了两次c，因此有最后一行代码b[x2 + 1][y2 + 1] += c;

b[i][j] += b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1]; 二维数组取前缀和。注意是 += 不是=，否则覆盖了原来的值。

样例

3 4 3
1 2 2 1
3 2 2 1
1 1 1 1
1 1 2 2 1
1 3 2 3 2
3 1 3 4 1

差分

$O(1)$

不通过差分，直接暴力的事件复杂度$o(n)$

y总代码

C++ 代码

/*
和一维差分类似。
一维差分是：b[l] += c; b[r + 1] -=c;
到了二维，由于是r+1 而不是r, 因此b[x2][y2]也取不到
  b[x1][y1] += c;
    b[x2 + 1][y1] -= c;
    b[x1][y2 + 1] -=c;
    b[x2 + 1][y2 + 1] += c;
*/
#include<iostream>
using namespace std;
const int N = 1010;
int b[N][N], a[N][N];
/*void insert(int x1, int y1, int x2, int y2, int c){
    b[x1][y1] += c;
    b[x2 + 1][y2] -= c;
    b[x2][y2 + 1] -=c;
    b[x2 + 1][y2 + 1] += c;
}*/

int main(){
    ios::sync_with_stdio(false);
    int n, m, q;
    cin >> n >> m >> q;
    /*初始化*/
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j)
            {
                cin >> a[i][j];
            }
    while(q--){
        int x1, x2, y1, y2, c;
        cin >> x1 >> y1 >> x2 >> y2 >> c;
        b[x1][y1] += c;
        b[x2 + 1][y1] -= c;
        b[x1][y2 + 1] -=c;
        b[x2 + 1][y2 + 1] += c;
    }
    /*shuchu */
    /*前缀和*/
    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] + a[i][j] << " ";
        }
        cout << endl;
    }

    return 0;
}