前缀和与差分

一，前缀和

前缀和是指某序列的前n项和，可以把它理解为数学上的数列的前n项和，而差分可以看成前缀和的逆运算。合理的使用前缀和与差分，可以将某些复杂的问题简单化。

1.1 一维前缀和

原理：

sum[r] = a[1] + a[2] + a[3] + a[l-1] + a[l] + a[l + 1] …… a[r];
sum[l - 1] = a[1] + a[2] + a[3] + a[l - 1];
sum[r] - sum[l - 1] = a[l] + a[l + 1] + ……+ a[r];

模板：

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
import java.util.Scanner;


public class Main {
    public static void main(String[] args) {

        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int[]arr=new int[n];
        int[]sn=new int[n];
        for (int i = 0; i < arr.length; i++) {
            arr[i]=sc.nextInt();
        }
        sn[0]=arr[0];
        for (int i = 1; i < arr.length; i++) {
            sn[i]=sn[i-1]+arr[i];
        }
        for (int i = 0; i < sn.length; i++) {
            System.out.println(sn[i]);
        }
        //        求l 到r 的区间和
        int l=sc.nextInt();
        int r=sc.nextInt();

        System.out.println(sn[r]-sn[l-1]);

    }
}

1.2二维前缀和

二维前缀和预处理公式

可以看成面积（集合），

s[i][j】为整个二维前缀和数组右下角的值，即可以看做整个面积

根据容斥原理可得：

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

若求区间（例如x1,y1到x2，y2的前缀和，则为x1,y1 x2,y2所围成的面积）

因此二维前缀和的结论为：

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

注意，构造矩阵的时候从arr【1】【1】开始，这样为了防止出现边界问题

例题：

输入一个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

输出样例：

17
27
21

代码：

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
#include <iostream>
using namespace std;
 
const int N= 1010;
 
int q[N][N];
 
int main(){
    int n, m, qn;
    
    scanf("%d %d %d", &n, &m, &qn);
    
    //一定要从1开始，不然边界问题好难处理
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            scanf("%d", &q[i][j]);
        }
    }
    
    int s[N][N];
    
    // 构建前缀和
    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]+q[i][j]; 
        }
    }
    
    int xa, ya, xb, yb;
    
    //区间更新
    while(qn--){
        scanf("%d %d %d %d", &xa, &ya, &xb, &yb);
        printf("%d\n", s[xb][yb] - s[xa-1][yb] -s[xb][ya-1] +s[xa-1][ya-1]);
    }
    
    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
43
44
45
46
47
48
49
50
51
52
53


import java.util.Scanner;


public class Main {
    public static void main(String[] args) {

        Scanner sc=new Scanner(System.in);

        int n=sc.nextInt();
        int m=sc.nextInt();
        int q=sc.nextInt();

        int[][]arr=new int[n+1][m+1];
        int[][]sn=new int[n+1][m+1];

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {

                arr[i][j]=sc.nextInt();
                sn[i][j]=arr[i][j];

            }
        }



        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                sn[i][j]+=sn[i][j-1]+sn[i-1][j]-sn[i-1][j-1];
//				      这里的+=在运算之前sn【i】【j】值为arr【i】【j】
//				sn[i][j]=arr[i][j]+sn[i][j-1]+sn[i-1][j]-sn[i-1][j-1];
//				arr[i][j]=sn[i][j]-sn[i][j-1]-sn[i-1][j]+sn[i-1][j-1]
            }
        }

while (q-->=0){
    int x1=sc.nextInt();

    int y1=sc.nextInt();

    int x2=sc.nextInt();

    int y2=sc.nextInt();

    System.out.println(sn[x2][y2]-sn[x2][y1-1]-sn[x1-1][y2]+sn[x1-1][y1-1]);


}

    }
}

二,差分

2.1.1一维差分

类似于数学中的求导和积分，差分可以看成前缀和的逆运算。

差分数组：

首先给定一个原数组a：a[1], a[2], a[3],,,,,, a[n];

然后我们构造一个数组b ： b[1], b[2], b[3],,,,,, b[i];

使得 a[i] = b[1] + b[2] + b[3] + ,,,,,, + b[i]

也就是说，a数组是b数组的前缀和数组，反过来我们把b数组叫做a数组的差分数组。换句话说，每一个a[i]都是b数组中从头开始的一段区间和。

考虑如何构造差分b数组？

最为直接的方法

如下：

a[0 ]= 0;

b[1] = a[1] - a[0];

b[2] = a[2] - a[1];

b[3] = a [3] - a[2];

……..

b[n] = a[n] - a[n - 1];

2.1.2差分数组的作用：

    也就是在O(n)的时间， 通过 b 差分数组 可以还原出他的 前缀和数组 a ，运用 差分的思想 可以很好的解决一类问题：

    例如给定一个区间 [l, r]  让a数组，这里边所有的数都加上c，如果是用遍历，那就需要O(n)的复杂度

    如果用差分来做，就可以做到O(1)原理如下:

  因为 ai = b1+ b2 + …+ bi  

  所以只需要对 b[l] 做 +c 的操作，那 a[l] 往后的数都会 +c

  又因为题目要求，只是 [l, r] 的区间，所以在对b[r+1] 做-c 的操作，相抵消，那 a[r+1] 之后的数就不会加上c了，

  这样再用b数组求前缀和，还原出的a数组 就是最后的结果

    所以只需要O(1)的时间就可以实现，以空间换时间

2.1.3例题

题目练习： AcWing 797. 差分

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

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

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

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

1
3 4 5 3 4 2

————————————————
代码实现：

java:

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
package org.example;

import java.util.Scanner;


public class Main {
    public static void main(String[] args) {

        Scanner sc=new Scanner(System.in);

        int n=sc.nextInt();
        int m=sc.nextInt();

        int[]arr=new int[n+100];
        int[]b=new int[n+100];

        for (int i = 1; i <= n; i++) {
            arr[i]=sc.nextInt();
//构建差分数组
            b[i]=arr[i]-arr[i-1];
        }


        while(m-->0) {

            int l=sc.nextInt();
            int r=sc.nextInt();
            int c=sc.nextInt();
//原数组是差分数组的前缀和数组，分别在差分数组的左右边界处分别加减c，会导致差分数组的前缀和数组除了边界值外的数保持不变
            b[l]=b[l]+c;
            b[r+1]=b[r+1]-c;


        }

        for (int i = 1; i <=n; i++) {
            arr[i]=b[i]+arr[i-1];
            System.out.print(arr[i]+"  ");
            
        }
    }
}

c++:

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
#include<iostream>
using namespace std;
const int N = 1e5 + 10;
int a[N],b[N]; 
int main()
{
    int n,m;
    scanf("%d%d", &n, &m);
    for(int i = 1;i <= n; i++) 
    {
        scanf("%d", &a[i]);
        b[i] = a[i] - a[i - 1];      //构建差分数组
    }
    int l, r, c;
    while(m--)
    {
        scanf("%d%d%d", &l, &r, &c);
        b[l] += c;     //表示将序列中[l, r]之间的每个数加上c
        b[r + 1] -= c;
    }
    for(int i = 1;i <= n; i++) 
    {
        b[i] += b[i - 1];  //求前缀和运算
        printf("%d ",b[i]);
    }
    return 0;
}

2.2.1二维差分

a[][]数组是b[][]数组的前缀和数组，那么b[][]是a[][]的差分数组

原数组： a[i][j]

我们去构造差分数组： b[i][j]

使得a数组中a[i][j]是b数组左上角(1,1)到右下角(i,j)所包围矩形元素的和。

已知原数组a中被选中的子矩阵为 以(x1,y1)为左上角，以(x2,y2)为右下角所围成的矩形区域;

始终要记得，a数组是b数组的前缀和数组，比如对b数组的b[i][j]的修改，会影响到a数组中从a[i][j]及往后的每一个数。

假定我们已经构造好了b数组，类比一维差分，我们执行以下操作
来使被选中的子矩阵中的每个元素的值加上c

b[x1][y1】 + = c ;

b[x1,][y2+1】- = c;

b[x2+1][y1】- = c;

b[x2+1][y2+1】+ = c;

图片详解：

https://img-blog.csdnimg.cn/20201217170336254.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ==,size_16,color_FFFFFF,t_70

每次对b数组执行以上操作，等价于：

1
2
3
4
for(int i = x1;i <= x2;i++)
  for(int j = y1;j <= y2;j++)
    a[i][j] += c;

2.2.2；例题

题目练习： AcWing 798. 差分矩阵
输入一个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
2
3
4
5
6
7
8
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
2 3 4 1
4 3 4 1
2 2 2 2

代码：

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72


import java.net.URL;
import java.util.Scanner;



public class Main {
static final  int N= 10010;
 static    int[][]arr=new int[N][N];
 static    int[][]b=new int[N][N];
    public static void main(String[] args) {

        Scanner sc=new Scanner(System.in);


        int n=sc.nextInt();
        int m=sc.nextInt();
        int q=sc.nextInt();


        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <=m ; j++) {
                arr[i][j]=sc.nextInt();
            }
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <=m ; j++) {

                b[i][j]=arr[i][j]-arr[i-1][j]-arr[i][j-1]+arr[i-1][j-1];

            }
        }

        while ((q--)>0){
            int x1= sc.nextInt();
            int y1= sc.nextInt();
            int x2= sc.nextInt();
            int y2= sc.nextInt();
            int c= sc.nextInt();

            insert(x1,y1,x2,y2,c);

        }
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= m; j++)
            {
                arr[i][j]=b[i][j]+arr[i-1][j]+arr[i][j-1]-arr[i-1][j-1];  //二维前缀和
            }
        }

        for (int i = 1; i <=n ; i++) {

            for (int j = 1; j <=m ; j++) {

                System.out.print(arr[i][j]+"  ");

            }
            System.out.println();
        }

    }
    public static 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;

    }
}