蓝桥杯JAVA-28.前缀和与差分详解

2023-11-05

import java.io.*;
import java.util.*;

/**
 * @Author DragonOne
 * @Date 2021/9/4 19:40
 */
public class Main {
    public static void main(String[] args) throws Exception {
        Scanner Scin = new Scanner(System.in);
        StreamTokenizer STcin = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        BufferedReader BRcin = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));

        final int m = (int) 1e2 + 5;
        int[][] s = new int[m][m];
        int[][] a = new int[m][m];
        for (int i = 1; i <= 5; i++) {
            for (int j = 1; j <= 5; j++) {
                a[i][j] = i + j;
                s[i][j] = s[i - 1][j] + s[i][j - 1] + a[i][j] - s[i - 1][j - 1];
            }
        }
        System.out.println("a数组为:");
        for (int i = 1; i <= 5; i++) {
            for (int j = 1; j <= 5; j++) {
                System.out.print(a[i][j] + " ");
            }
            System.out.println();
        }
        System.out.println("s数组为:");
        for (int i = 1; i <= 5; i++) {
            for (int j = 1; j <= 5; j++) {
                System.out.print(s[i][j] + " ");
            }
            System.out.println();
        }
        System.out.println("(2,2)到(4,3)的矩阵和为：");
        int x1, x2, y1, y2;
        x1 = 2;
        y1 = 2;
        x2 = 4;
        y2 = 3;
        System.out.println("s[x2][y2]: " + s[x2][y2]);
        System.out.println("s[x1 - 1][y2]: " + s[x1 - 1][y2]);
        System.out.println("s[x2][y1 - 1]: " + s[x2][y1 - 1]);
        System.out.println("s[x1 - 1][y1 - 1]: " + s[x1 - 1][y1 - 1]);
        System.out.println(s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]);

    }
}

输出：

a数组为:
2 3 4 5 6 
3 4 5 6 7 
4 5 6 7 8 
5 6 7 8 9 
6 7 8 9 10 
s数组为:
2 5 9 14 20 
5 12 21 32 45 
9 21 36 54 75 
14 32 54 80 110 
20 45 75 110 150 
(2,2)到(4,3)的矩阵和为：
s[x2][y2]: 54
s[x1 - 1][y2]: 9
s[x2][y1 - 1]: 14
s[x1 - 1][y1 - 1]: 2
33

2.差分

差分可以看成前缀和的逆运算。类似于积分和微分。

2.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数组，通过前缀和运算，就可以在O(n) 的时间内得到a数组。

至于考虑如何构造差分b数组。这个我们现在不需要关心，其实也没有必要关心如何构造b数组。往后面看就明白为什么了。

差分原理

首先，需要知道两个数组，一个原数组a，一个差分数组b。

首先明白的是，a数组是b数组的前缀和，b数组是a数组的差分数组。即b数组相当于是原数组，a数组是b数组的前缀和。

明白后，想一个问题。如果b[1]加上1，那么a数组怎么变？是不是a[1]及后面的所有数都会加上1。因为a数组是b数组的前缀和，a[i]存的是b的前i个数的和。

即：差分b数组中的 b[i] + c ,通过前缀和运算后，a数组变成 a[i] + c ,a[i+1] + c, a[n] + c;
最好自行在纸上画画。

好。明白上面后。单个修改没问题了。那我们再来算一个区间的。把a数组中的[ l, r]区间中的每一个数都加上c。

最容易想到的就是对b[l]+c，那么a[l]及其后面的数都加上了c。然后对b[r]+c吗？这不是就不对了嘛。
对a[r+1]-c即可，那么a[r+1]及其后面的都减去了c，就把前面加的抵消了。见图。

b[l] + c，效果使得a数组中 a[l]及以后的数都加上了c(红色部分)，但我们只要求l到r区间加上c, 因此还需要执行 b[r+1] - c,让a数组中a[r+1]及往后的区间再减去c(绿色部分)，这样对于a[r] 以后区间的数相当于没有发生改变。

一维差分结论：给a数组中的[ l, r]区间中的每一个数都加上c,只需对差分数组b做 b[l] + = c, b[r+1] - = c即可。

这就是一维差分数组。

差分数组的构造

前面说了，这个不需要我们关心的。只需要明白了上面的原理即可。因为，我们只需要把原数组a中的数也当成是要操作的数即可。

即，我们一开始可以把a数组和b数组都当成0，即a、b数组全是0。然后，对于每一个a数组中的数，我们都可以看成是一次修改，进而在b数组中进行操作。例如，a[1]=3，a[2]=10。即，在b数组的区间[1,1]中加上3，b数组的区间[2,2]中加上10。

所以，对于差分数组如何构造，我们无需知道。

示例：

import java.io.*;
import java.util.*;

/**
 * @Author DragonOne
 * @Date 2021/9/4 19:40
 */
public class Main {
    public static final int m = (int) 1e2 + 5;
    public static int[] b = new int[m];
    public static int[] a = new int[m];

    public static void main(String[] args) throws Exception {
        Scanner Scin = new Scanner(System.in);
        StreamTokenizer STcin = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        BufferedReader BRcin = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));

        for (int i = 1; i <= 10; i++) {
            a[i] = i;
        }
        System.out.println("a数组为：");
        for (int i = 0; i < 10; i++) {
            System.out.print(a[i + 1] + " ");
        }
        System.out.println();

        for (int i = 1; i <= 10; i++) {
            insert(i, i, a[i]);
        }
        System.out.println("b数组为：");
        for (int i = 1; i <= 10; i++) {
            System.out.print(b[i] + " ");
        }
        System.out.println();
    }

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

输出：

a数组为：
1 2 3 4 5 6 7 8 9 10 
b数组为：
1 1 1 1 1 1 1 1 1 1

当然了，如果非要自己去构造的话也是可以的，这里也提供一种构造方法。

如下：
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.2 二维差分

同理在二维中，a[][]数组是b[][]数组的前缀和数组，那么b[][]是a[][]的差分数组。至于差分数组的构造在一维中已经说的很明白了。

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

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

原理

先看一张区域分割图：

再来看具体的分割：

b[x1][ y1 ] +=c ; 对应编号图1 ,让整个a数组中蓝色矩形面积的元素都加上了c。
b[x1][y2+1]-=c ; 对应编号图2 ,让整个a数组中绿色矩形面积的元素再减去c，使其内元素不发生改变。
b[x2+1][y1]- =c ; 对应编号图3 ,让整个a数组中紫色矩形面积的元素再减去c，使其内元素不发生改变。
b[x2+1][y2+1]+=c; 对应编号图4,让整个a数组中红色矩形面积的元素再加上c，红色内的相当于被减了两次，再加上一次c，才能使其恢复。

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

实现：

void insert(int x1,int y1,int x2,int y2,int c)
{     //对b数组执行插入操作，等价于对a数组中的(x1,y1)到(x2,y2)之间的元素都加上了c
    b[x1][y1]+=c;
    b[x2+1][y1]-=c;
    b[x1][y2+1]-=c;
    b[x2+1][y2+1]+=c;
}

当然了，二维差分操作也有直接的构造方法，公式如下：
b[i][j]=a[i][j]−a[i−1][j]−a[i][j−1]+a[i−1][j−1]

构造同一维差分那里的思维相同。这里不再说了。

这就是二维差分。

3.总结

一句话：前缀和受影响的向前看，差分受影响的向后看。

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)