題目

差分矩陣

題解

只有一個(gè)操作：

void insert(int x1, int y1, int x2, int y2, int c){b[x1][y1] += c;b[x2 + 1][y1] -= c;b[x1][y2 + 1] -= c;b[x2 + 1][y2 + 1] += c;
}

利用差分的思想，擴(kuò)展到二維上。
insert函數(shù)作用是將矩陣之內(nèi)的數(shù)全部加上c， 其余部分不會(huì)變。
而最后的實(shí)現(xiàn)其實(shí)就是前面子矩陣的和這道題的方法，也就是將最后得到的b數(shù)組進(jìn)行二維前綴和的操作,
得到的b數(shù)組就是答案

舉例理解：

	首先 假設(shè) 有一個(gè)4X4 的小方塊要加上 2， 那么我們先將方塊的左上角(1, 1)加上2。然后你想，我們最后是要進(jìn)行二維前綴和的運(yùn)算的，那么為了不讓其它部分受到影響，我們要將（1, 5）（5, 1）上的數(shù)減去2，抵消從（1， 1）傳遞過(guò)來(lái)的2的影響，這樣后面的數(shù)也不會(huì)受到影響了。注意！有一個(gè)位置，就是b（5, 5）它減去了兩次2！因?yàn)樗瑫r(shí)受b（5， 1）b（1， 5）的影響，所以我們還要在b（5， 5）再加上2.

代碼

答案

#include <bits/stdc++.h>
using namespace std;
const int N = 1010;int n, m, q;
int a[N][N], b[N][N];void insert(int x1, int y1, int x2, int y2, int c){b[x1][y1] += c;b[x2 + 1][y1] -= c;b[x1][y2 + 1] -= c;b[x2 + 1][y2 + 1] += c;
}int main(){scanf("%d%d%d", &n, &m, &q);for(int i = 1; i <= n; i ++)for(int j = 1;j <= m; j ++){scanf("%d", &a[i][j]);insert(i, j, i, j, a[i][j]);}for(int i = 1; i <= q; i ++){int x1, x2, y1, y2, c;scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &c);insert(x1, y1, x2, y2, c);}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];for(int i = 1; i <= n; i ++){for(int j = 1; j <= m; j ++)printf("%d ", b[i][j]);puts("");}    return 0;
}