前缀和&差分

前缀和

前缀和是指某序列的前n项和,而差分则可以看成前缀和的逆运算。

一维前缀和

例题

输入一个长度为 n 的整数序列。

接下来再输入 m 个询问,每个询问输入一对 l, r 。

对于每个询问,输出原序列中从第 l 个数到第 r 个数的和。

输入格式

第一行包含两个整数 n 和 m。

第二行包含 n 个整数,表示整数数列。

接下来 m 行,每行包含两个整数 l 和 r,表示一个询问的区间范围。

输出格式

共 m 行,每行输出一个询问的结果。

输入样例:

5 3
2 1 3 6 4
1 2
1 3
2 4

输出样例:

3
6
10

代码实现:

 1 #include <iostream>
 2 using namespace std;
 3 
 4 const int N = 1e5 + 10;
 5 int sum[N];//前缀和数组
 6 
 7 int main(){
 8     //n个数,q对查询
 9     int n, q;
10     cin >> n >> q;
11     for (int i = 0; i < n;i++){
12         int num;
13         //使用scanf增加读入效率
14         scanf("%d", &num);        
15         //构造前缀和数组
16         sum[i] = i == 0 ? num : sum[i - 1] + num;
17     }
18     while(q--){
19         int l,r;
20         scanf("%d%d", &l, &r);
21         //利用前缀和输出结果
22         printf("%d\n", sum[r] - sum[l - 1]);
23     }
24     return 0;
25 }

二维前缀和

对于下面一道例题:

输入一个 n 行 m 列的整数矩阵,再输入 q 个询问,每个询问包含四个整数 x1,y1,x2,y2。表示一个子矩阵的左上角坐标和右下角坐标。

对于每个询问输出子矩阵中所有数的和。

 

1、首先预处理出二维前缀和

前缀和&差分

如图,蓝色矩形为我们所求的(i,j)位置的前缀和。蓝色面积 = 绿色面积 + 紫色面积 - 红色面积 + 小方块面积

因此得出二维前缀和预处理公式

s[i][j] = s[i-1][j] + s[i][j-1 ] + a[i][j] - s[i-1][j-1]

 

2、然后求子矩阵的面积

前缀和&差分

 

如图,绿色矩形的面积即为所求。绿色面积 = 整个的蓝色面积 - 黄色面积 - 紫色面积 + 红色面积(被重复减去)

所以以(x1, y1)为左上角,(x2, y2)为右下角的子矩阵的和为:
s[x2, y2] - s[x1 - 1, y2] - s[x2, y1 - 1] + s[x1 - 1, y1 - 1]

完整例题

 

输入一个 nn 行 mm 列的整数矩阵,再输入 qq 个询问,每个询问包含四个整数 x1,y1,x2,y2x1,y1,x2,y2,表示一个子矩阵的左上角坐标和右下角坐标。

 

对于每个询问输出子矩阵中所有数的和。

 

输入格式

 

第一行包含三个整数 n,m,q 。

 

接下来 n 行,每行包含 m 个整数,表示整数矩阵。

 

接下来 q 行,每行包含四个整数 x1,y1,x2,y2。表示一组询问。

 

输出格式

 

共 q 行,每行输出一个询问的结果。

 

输入样例:

 

3 4 3
1 7 2 4
3 6 2 8
2 1 2 3
1 1 2 2
2 1 3 4
1 3 3 4

 

输出样例:

 

17
27
21

 

代码实现:

 1 #include <iostream>
 2 using namespace std;
 3 
 4 const int N = 1010;
 5 int a[N][N], s[N][N];
 6 
 7 int main() {
 8     int n, m, q;
 9     cin >> n >> m >> q;
10 
11     for (int i = 1; i <= n; i++)
12         for (int j = 1; j <= m; j++) {
13             scanf("%d", &a[i][j]);
14             // 求前缀和
15             s[i][j] = s[i][j - 1] + s[i - 1][j] - s[i - 1][j - 1] + a[i][j];
16             //s[i][j] = s[i][j - 1] + s[i - 1][j] - s[i - 1][j - 1] + s[i][j];
17         }
18 
19     while (q--) {
20         int x1,y1,x2,y2;
21         scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
22         //子矩阵的和
23         printf("%d\n", s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1]); 
24     }
25 
26     return 0;
27 }

差分

差分实质上就是前缀和的逆运算过程

一维差分

在一个数组中,有n个操作,每个操作把【l , r 】的每个元素 + c(或者 - c)

前缀和&差分

 

 

 

1、构造一个差分数组d [ ],d[ n ] = a[ n ] - a[n - 1]

2、在差分数组打上标记,使d[ l ] + c,d[ r ] - c

3、求标记后的差分数组的前缀和数组 s [ ]

 

完整例题

输入一个长度为 n 的整数序列。

接下来输入 m 个操作,每个操作包含三个整数 l,r,c,表示将序列中 [l, r]之间的每个数加上 c。

请你输出进行完所有操作后的序列。

输入格式

第一行包含两个整数 n 和 m。

第二行包含 n 个整数,表示整数序列。

接下来 m 行,每行包含三个整数 l,r,c,表示一个操作。

输出格式

共一行,包含 n 个整数,表示最终序列。

输入样例:

6 3
1 2 2 1 2 1
1 3 1
3 5 1
1 6 1

输出样例:

3 4 5 3 4 2

代码实现:

 1 #include<iostream>
 2 using namespace std;
 3 
 4 const int N = 1e5 + 10;
 5 int a[N], d[N];
 6 
 7 int main()
 8 {
 9     int n, m;
10     scanf("%d%d", &n, &m);
11     for (int i = 1; i <= n; i++){
12         scanf("%d", &a[i]);
13         //构建差分数组
14         d[i] = a[i] - a[i - 1];
15     }
16     int l, r, c;
17     while (m--){
18         scanf("%d%d%d", &l, &r, &c);
19         //打上标记
20         d[l] += c;
21         d[r + 1] -= c;
22     }
23     for (int i = 1; i <= n; i++){
24         //前缀和运算
25         d[i] += d[i - 1];
26         printf("%d ", d[i]);
27     }
28     return 0;
29 }

二维差分

让二维数组中左上角坐标为 (x1, y2), 右下角坐标为 (x2, y2) 的子矩阵中的每个元素的值加上c(或者减去c)。

整体思想和一维差分一样。关键在于以下两点

1、构造二维差分数组

  • 我们可以先假想a数组为空,那么d数组一开始也为空,但是实际上a数组并不为空,因此我们每次让以(i,j)为左上角到以(i,j)为右下角面积内元素(其实就是一个小方格的面积)去插入 c=a[i][j],等价于原数组a中(i,j) 到(i,j)范围内 加上了 a[i][j] ,因此执行n*m次插入操作,就成功构建了差分d数组.

  • 直接构造:d[i][j]=a[i][j]−a[i−1][j]−a[i][j−1]+a[i−1][j−1]

2、对差分数组打上标记

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

前缀和&差分

 

完整例题

输入一个 nn 行 mm 列的整数矩阵,再输入 q 个操作,每个操作包含五个整数 x1,y1,x2,y2,c,其中 (x1,y1)和  (x2,y2) 表示一个子矩阵的左上角坐标和右下角坐标。

每个操作都要将选中的子矩阵中的每个元素的值加上 c。

请你将进行完所有操作后的矩阵输出。

输入格式

第一行包含整数 n,m,qn,m,q。

接下来 n 行,每行包含 m 个整数,表示整数矩阵。

接下来 q 行,每行包含 5 个整数 x1,y1,x2,y2,c, 表示一个操作。

输出格式

共 n 行,每行 m 个整数,表示所有操作进行完毕后的最终矩阵。

输入样例:

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

输出样例:

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

代码实现:

方法一:

先构建差分标记数组(默认为0),再求差分标记数组的前缀和数组,再将前缀和数组与原数组结合求值

 1 #include <iostream>
 2 
 3 using namespace std;
 4 const int N = 1010;
 5 int arr[N][N], d[N][N];
 6 
 7 void change(int x1,int y1,int x2,int y2,int c){
 8     d[x1][y1] += c;
 9     d[x2 + 1][y1] -= c;
10     d[x1][y2 + 1] -= c;
11     d[x2 + 1][y2 + 1] += c;
12 }
13 
14 int main() {
15     int n,m,q;
16     cin >> n >> m >> q;
17     for (int i = 0; i < n;i++)
18         for (int j = 0; j < m;j++)
19             scanf("%d", &arr[i][j]);
20     cout << endl;
21     //构建差分标记数组
22     while(q--){
23         int x1, y1, x2, y2, c;
24         scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &c);
25         change(x1, y1, x2, y2, c);
26     }
27 
28     //求差分标记数组的前缀和数组
29     for (int i = 1; i <= n; i++)
30         for (int j = 1; j <= m; j++) {
31             d[i][j] += d[i - 1][j] + d[i][j - 1] - d[i - 1][j - 1]; // 求前缀和
32         }
33 
34     //将求出来的前缀和数组与原数组结合
35     for (int i = 0; i < n + 1; i++)
36         for (int j = 0; j < m + 1; j++)
37             arr[i][j] += d[i + 1][j + 1];//根据题意适当考虑i+1,j+1
38     
39     //打印输出操作后的数组
40     for (int i = 0; i < n; i++)
41     {
42         for (int j = 0; j < m; j++)
43             printf("%d ", arr[i][j]);
44         cout << endl;
45     }
46     return 0;
47 }
方法二:

先求差分数组,再打标记,再求前缀和

 1 #include <iostream>
 2 using namespace std;
 3 
 4 const int N = 1010;
 5 
 6 int n, m, q;
 7 int a[N][N], b[N][N];
 8 
 9 void insert(int x1, int y1, int x2, int y2, int c)
10 {
11     b[x1][y1] += c;
12     b[x2 + 1][y1] -= c;
13     b[x1][y2 + 1] -= c;
14     b[x2 + 1][y2 + 1] += c;
15 }
16 
17 int main()
18 {
19     scanf("%d%d%d", &n, &m, &q);
20     //读入矩阵
21     for (int i = 1; i <= n; i ++ )
22         for (int j = 1; j <= m; j ++ )
23             scanf("%d", &a[i][j]);
24 
25     //构造差分数组
26     for (int i = 1; i <= n; i ++ )
27         for (int j = 1; j <= m; j ++ )
28             insert(i, j, i, j, a[i][j]);
29 
30     //差分标记
31     while (q -- )
32     {
33         int x1, y1, x2, y2, c;
34         cin >> x1 >> y1 >> x2 >> y2 >> c;
35         insert(x1, y1, x2, y2, c);
36     }
37 
38     //求前缀和数组
39     for (int i = 1; i <= n; i ++ )
40         for (int j = 1; j <= m; j ++ )
41             b[i][j] += b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1];
42 
43     //输出结果矩阵
44     for (int i = 1; i <= n; i ++ )
45     {
46         for (int j = 1; j <= m; j ++ ) 
47             printf("%d ", b[i][j]);
48         cout << endl;
49     }
50 
51     return 0;
52 }
上一篇:ps裁剪图形


下一篇:敬伟PS教程:掌握篇B07高级抠图