差分算法总结

差分是前缀和的逆运算

一维差分

对于a₁，a₂，…，a_n，构造b₁，b₂，…，b_n，使得a_i = b₁ + b₂ + … + b_i。此时，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 = (a_ij)_n*m，差分矩阵为B = (b_ij)_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 }