图文轻松弄懂一二维的前缀和与差分_二维前缀和差分

---

前缀和

输入一个长度为 n 的整数序列。
接下来再输入 m 个询问，每个询问输入一对 l,r。
对于每个询问，输出原序列中从第 l 个数到第 r 个数的和。

输入格式
第一行包含两个整数 n 和 m。
第二行包含 n 个整数，表示整数数列。
接下来 m 行，每行包含两个整数 l 和 r，表示一个询问的区间范围。

输出格式
共 m 行，每行输出一个询问的结果。

数据范围
1≤l≤r≤n,
1≤n,m≤100000,
−1000≤数列中元素的值≤1000

输入样例：

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

输出样例：

3
6
10
1
2
3

---

这是一个一维的前缀和问题，对于序列a，如果用朴素的做法求其 [l，r] 区间的元素和，就是 l 到 r 扫描一遍然后累加各项元素，其复杂度为O(n) 。
那么前缀和的做法就是类似与高中数列求和思想，定义一个s，使得s[i] = a[1] + a[2] + ... + a[i]，这样一来，如果要求a[l，r] 的和，只需要求s[r + 1] -s[l]便等于最终结果，因为根据定义：s[r] - s[l - 1] = a[l] + ... + a[r]。所以这样做使得复杂度降为O(1)。

---

C++代码

#include <iostream>
#include <cstring>
using namespace std;

const int N = 100010;

int n, m, l, r;;
int a[N], s[N];

int main(){
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ ) 		cin >> a[i];
    for (int i = 1; i <= n; i ++ )  s[i] = s[i - 1] + a[i]; // 前缀和的初始化

    while (m -- ){
        cin >> l >> r;
        printf("%d\n", s[r] - s[l - 1]); 		//区间和的计算
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

---

子矩阵的和

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

输入格式
第一行包含三个整数 n，m，q。
接下来 n 行，每行包含 m 个整数，表示整数矩阵。
接下来 q 行，每行包含四个整数 x1,y1,x2,y2，表示一组询问。

输出格式
共 q 行，每行输出一个询问的结果。

数据范围
1≤n,m≤1000,
1≤q≤200000,
1≤x1≤x2≤n,
1≤y1≤y2≤m,
−1000≤矩阵内元素的值≤1000

输入样例：

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
1
2
3
4
5
6
7

输出样例：

17
27
21
1
2
3

---

问题从一维转变成了二维，倘若利用朴素做法，i 一层循环 j 一层循环会使得其复杂度为O(n^2)，再加上n次查询，耗费的时间为 O(N^3)。
仍然使用前缀和做法，定义a[n][m]表示这个n行m列的矩阵，其前缀和矩阵为s[n][m]。这时s[i][j]的含义是指，以左上角为点 (1,1)，右下角为点 (i，j) 的子矩阵所有元素之和，也就是s[i][j] = a[1][1] + ... + a[1][j] + ... + a[i][1] + ... + a[i][j]，下图可以直观理解

---

每个网格表示的是矩阵a的对应元素，其中蓝色区域求和即为s(i，j)。
注： 一二维的前缀和都是从1开始的，下标关于0的元素恒为0，二维中用 i 表示行，j 表示列。

---

已经知道一维的前缀和递推式是s(i) = s(i - 1) + a(i)，那么二维的递推式则是s(i，j) = s(i - 1，j) + s(i，j - 1) - s(i - 1，j - 1) + s(i，j)，直观上可能不太好理解，下图则一目了然了。

---

图一中蓝色的区域可以看作由图二的四种颜色区域共同组合而成，类似于区域面积计算。
根据相关定义，我们可以从图中得知：

紫色 = s(i，j - 1) - 棕色 。
黄色 = s(i - 1，j ) - 棕色 。
棕色 = s(i - 1，j - 1)。
绿色 = a(i，j )。

由于已经存在了如下的关系：
图1：蓝色 = 图2：紫色 + 黄色 + 棕色 + 绿色
进一步将等式带入即可得到：
s(i，j) = s(i - 1，j) + s(i，j - 1) - s(i - 1，j - 1) + s(i，j)。

---

有了前缀和初始化的方法，接下来就是求 (x1,y1) 与 *(x2,y2)*围成的子矩阵各元素之和，仍然利用刚刚分块化的思想，假设要求的某个子矩阵区域如下图：

然后，给出如下的区域：

---

结合两图，可以得到的大关系为：s(x2，y2) - 蓝色 = 棕色 + 绿色 + 紫色
而目标要求的是：蓝色区域 = s(x2，y2) - 棕色 - 绿色 - 紫色
再从图中可以看出的关系有：

棕色 = s( x1 - 1，y1- 1) 。
紫色 = s( x2，y1 - 1) - 棕色 。
绿色 = s( x1 - 1，y2 ) - 棕色 。

然后，接下来就只管代入就可以得出等式为：
蓝色区域 = 子矩阵a[(x1,y1)—>(x2,y2)]元素和 = s(x2，y2) - s( x2，y1 - 1) - s( x1 - 1，y2 ) + s( x1 - 1，y1- 1)。

---

C++代码

#include <iostream>
#include <cstring>
using namespace std;

const int Max = 1010;

int s[Max][Max];
int n, m, q, x1, y1, x2, y2;

/*
从(1,1)开始，对于i × j = 0的坐标对应值恒为0
*/

int main(){
    cin >> n >> m >> q;
    for(int i = 1;i <= n;i ++)
        for(int j = 1;j <= m;j ++)
            cin >> s[i][j];
    
    for(int i = 1;i <= n;i ++)
        for(int j = 1;j <= m;j ++)
            s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + s[i][j];
        
    while(q --){
        cin >> x1 >> y1 >> x2 >> y2;
        cout << s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1] << endl;
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

可以只使用一个二维数组来存储，因为前面的元素被加到s上后将不再读取矩阵a里的元素。

---

差分

输入一个长度为 n 的整数序列。
接下来输入 m 个操作，每个操作包含三个整数 l,r,c，表示将序列中 [l,r] 之间的每个数加上 c。
请你输出进行完所有操作后的序列。

输入格式
第一行包含两个整数 n 和 m。
第二行包含 n 个整数，表示整数序列。
接下来 m 行，每行包含三个整数 l，r，c，表示一个操作。

输出格式
共一行，包含 n 个整数，表示最终序列。

数据范围
1≤n,m≤100000,
1≤l≤r≤n,
−1000≤c≤1000,
−1000≤整数序列中元素的值≤1000

输入样例：

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

输出样例：

3 4 5 3 4 2
1

---

差分本质上可以理解为前缀和的逆运算，假设通过求数组b[]的各个元素的和来得到a[]，然后称a[]为b[]的前缀和数组(a[i] = b[1] + b[2 ]+ ... + b[i])，那么反过来可以称b[]是a[]的差分数组。
而差分其实就是在并不知道b[]的情况下，给定了前缀和数组a[]，进而逆操作得出b[]。
根据上述定义很显然有：

a[i] = b[1] + b[2] + ... + b[i - 1] + b[i]
a[i - 1] = b[1] + b[2] + ... + b[i - 1]

所以得出差分数组各元素的求法：b[i] = a[i] - a[i - 1]。

---

对于本题，朴素做法是对a[]中每个 [l，r] 之间的元素遍历并进行＋c 操作，其复杂度为O(n)，而差分在这里可以通过操作b[]来间接影响a[]，将其复杂度降到O(1)。
首先要明确的是对于b[i]的修改是会影响a[i]及其后面(直到末尾)每一个数的，例如b[i] + c，则a[]从i开始的各个元素会变成a[i] + c，a[i + 1] + c，…，a[n] + c，道理很简单，因为a是由b垒起来的。而这题目的是只对a[l]...a[r]操作，对b[l] + c会使得从a[r + 1]开始后面的每个数也＋c，因此还需要打一个“补丁”，即b[r + 1] - c，于是从a[r + 1]开始后面的每个数变成了＋c - c = 0 抵消掉了，下图方便理解，对b[]操作完之后接下来只需再求一次前缀和就得到了更新后的a[]。

---

总结一句话就是：给a数组中的[l, r]区间中的每一个数都加上c,只需对差分数组b做 b[l] += c, b[r + 1] - = c。时间复杂度为O(1), 大大提高了效率。

---

C++代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

int n, m, l, r, c;
int a[100010], b[100010];

void insert(int l, int r, int c){
    b[l] += c;
    b[r + 1] -= c;
}

int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; i ++){
         cin >> a[i];
         b[i] = a[i] - a[i - 1];        //b[i]与a[i]的关系
    }
    
    while(m --){
        cin >> l >> r >> c;
        insert(l, r, c);
    }
    
    for(int i = 1;i <= n;i ++){
        a[i] = b[i] + a[i - 1];     //更新a[i]
        cout << a[i] << " ";
    }
    
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

---

差分矩阵

输入一个 n 行 m 列的整数矩阵，再输入 q 个操作，每个操作包含五个整数 x1,y1,x2,y2,c，其中 (x1,y1) 和 (x2,y2) 表示一个子矩阵的左上角坐标和右下角坐标。
每个操作都要将选中的子矩阵中的每个元素的值加上 c。
请你将进行完所有操作后的矩阵输出。

输入格式
第一行包含整数 n,m,q。
接下来 n 行，每行包含 m 个整数，表示整数矩阵。
接下来 q 行，每行包含 5 个整数 x1,y1,x2,y2,c，表示一个操作。

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

数据范围
1≤n,m≤1000,
1≤q≤100000,
1≤x1≤x2≤n,
1≤y1≤y2≤m,
−1000≤c≤1000,
−1000≤矩阵内元素的值≤1000

输入样例：

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
1
2
3
4
5
6
7

输出样例：

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

---

只要思想掌握了，到这里基本就是换汤不换药的做法，只不过又是从一维变到了二维进行处理，仍然定义b[][]为a[][]的差分数组，这题重点是子矩阵 (x1，y1)—>(x2，y2) 上如何合理地表示b[][]的更新操作，如图所示，表示的是a[][]

---

题意是想对于每组 (x1，y1)和 (x2，y2)，对应于图中蓝色区域中的各个元素进行 +c 操作，
在有了b[x1][y1] += c操作之后，紫色圈起来的区域内元素都会 +c ，因此打补丁希望绿色区域和棕色区域能够 -c后于 +c抵消，直观的想法是先进行b[x1][y2 + 1] -= c、b[x2 + 1][y1] -= c这两个操作，这样绿色区域就补上了，但又注意到棕色区域被 +c 了一次，-c了两次，表征出来的就是 -c，所以希望对棕色区域再打一个补丁来弥补，那就最后在执行b[x2 + 1][y2 + 1] += c操作，这样也就确保只有蓝色区域最终在a[][]上的表现是 +c。
结合以上四种操作，这就是二维差分上的insert操作。

---

C++代码

#include <iostream>
#include <cstring>
using namespace std;

const int M = 1010;

int n, m, q;
int a[M][M], b[M][M];
int x1, y1, x2, y2, c;

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

int main(){
    ios::sync_with_stdio(false);
    cin >> n >> m >> q;
    for (int i = 1; i <= n;i ++)
        for(int j = 1;j <= m;j ++){
            cin >> a[i][j];
            insert(i, j, i, j, a[i][j]);		//初始化构造差分数组
        }
    
    while(q --){
        cin >> 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 ++){
            a[i][j] = a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1] + b[i][j];		
            //利用b来更新a
            printf("%d ", a[i][j]);
        }
        puts("");
    }

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42