差分是前缀和的逆运算
一维差分
对于a1，a2，…，an，构造b1，b2，…，bn，使得ai = b1 + b2 + … + bi。此时，b数组成为a数组的差分，a数组称为b数组的前缀和。
题目链接：
https://www.acwing.com/problem/content/799/
代码模版：
1 #include <iostream> 2 3 using namespace std; 4 5 const int N = 100010; 6 7 int n, m, x; 8 int b[N]; 9 10 void insert(int l, int r, int c) 11 { 12 b[l] += c; 13 b[r + 1] -= c; 14 } 15 16 int main() 17 { 18 scanf("%d%d", &n, &m); 19 for (int i = 1; i <= n; i++) 20 { 21 scanf("%d", &x); 22 insert(i, i, x); 23 } 24 25 while (m--) 26 { 27 int l, r, c; 28 scanf("%d%d%d", &l, &r, &c); 29 insert(l, r, c); 30 } 31 32 for (int i = 1; i <= n; i++) 33 { 34 b[i] += b[i - 1]; 35 printf("%d ", b[i]); 36 } 37 38 return 0; 39 }
二维差分
原矩阵为A = (aij)n*m，差分矩阵为B = (bij)n*m，使得矩阵A是差分矩阵B的前缀和。
初始化：令矩阵A = O，那么矩阵B = O。然后把矩阵A中的每个元素依次插入。
题目链接：
https://www.acwing.com/problem/content/800/
代码模版：
1 #include <iostream> 2 3 using namespace std; 4 5 const int N = 1010; 6 7 int n, m, q, x; 8 int b[N][N]; 9 10 void insert(int x1, int y1, int x2, int y2, int c) 11 { 12 b[x1][y1] += c; 13 b[x2 + 1][y1] -= c; 14 b[x1][y2 + 1] -= c; 15 b[x2 + 1][y2 + 1] += c; 16 } 17 18 int main() 19 { 20 scanf("%d%d%d", &n, &m, &q); 21 22 for (int i = 1; i <= n; i++) 23 for (int j = 1; j <= m; j++) 24 { 25 scanf("%d", &x); 26 insert(i, j, i, j, x); 27 } 28 29 while (q--) 30 { 31 int x1, y1, x2, y2, c; 32 scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &c); 33 insert(x1, y1, x2, y2, c); 34 } 35 36 for (int i = 1; i <= n; i++) 37 { 38 for (int j = 1; j <= m; j++) 39 { 40 b[i][j] += b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1]; 41 printf("%d ", b[i][j]); 42 } 43 puts(""); 44 } 45 46 return 0; 47 }