差分 | 东川

差分

$a_1,a_2,a_3 ... \\ b_1,b_2,b_3... \\ a_i = b_1 + b_2 +...b_i$

a就称为b的前缀和，b就称为a的差分

一维差分

差分解决的一类问题：

表示将序列中[l, r]之间的每个数加上c。

序列本身是前缀和，弄一个差分即可

插入操作

b[l] += val;
b[r+1] -= val;

模板

import java.io.*
public class Main {
    
    public static void insert(int l, int r, int val){
		b[l] += val;
		b[r+1] -= val;
	}
	
    static int N = 100010;  // 数据规模为 10w
    static int[] b = new int[N];    // b数组为 arr数组的差分
    static int[] arr = new int[N];  // arr数组为 b数组的前缀和
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String[] str1 = br.readLine().split(" ");
		//数列 a[n] m询问次数
		int n = Integer.parseInt(str1[0]);
		int m = Integer.parseInt(str1[1]);
		
		
		String[] str2 = br.readLine().split(" ");
		for(int i=1;i<=n;i++)
		{
			arr[i]=Integer.parseInt(str2[i-1]); //arr[i] 从1开始
		}    
        
        for(int i=1;i<=n;i++){
            // 相当于将 arr中全部看为 0, 则 b[n]中也全部都为 0, 
			//再在其中区间 [i, i] 添加 arr[i], 求出 b[i]
            // i-i 之间插入
            insert(i,i,arr[i]);
        }
        
        //m次操作
        for(int i=0;i<m;i++){
            String[] sIn = br.readLine().split(" ");
            int l = Integer.parseInt(sIn[0]), r = Integer.parseInt(sIn[1]), val = Integer.parseInt(sIn[2]);
            insert(l, r, val);
        }
        
        //求插入后的和，即前缀和 求前缀和 ，这里的b其实是s[i]
		for(int i=1;i<=n;i++)
		{
			b[i] += b[i-1];
		}
		
		for(int i=1;i<=n;i++)
		{
			System.out.print(b[i]+" ");
		}
    }
}

二维差分

核心：

插入操作

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

模板

import java.util.Scanner;

public class Main {
    private static int N = 1010;
    private static int[][] b;

    public static void main(String[] args) {
        // 输入数据初始化
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        int q = in.nextInt();
        b = new int[N][N];
        int[][] arr = new int[N][N];
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
                arr[i][j] = in.nextInt();
        // 打印输入二维数组
        // printArr(arr, n, m);


        // 插入数组
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
                insert(i, j, i, j, arr[i][j]);

        // 循环插入
        while (q-- > 0) {
            int x1 = in.nextInt();
            int y1 = in.nextInt();
            int x2 = in.nextInt();
            int y2 = in.nextInt();
            int c = in.nextInt();
            // 插入操作, 对 b[n]造成影响
            insert(x1, y1, x2, y2, c);
        }


        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
                // 理解理解
                arr[i][j] = arr[i - 1][j] + arr[i][j - 1] - arr[i - 1][j - 1] + b[i][j];

        // 打印结果
        printArr(arr, n, m);


    }

    // 进行插入操作
    private 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;
    }

    // 打印二维数组
    private static void printArr(int[][] arr, int n, int m) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                System.out.print(arr[i][j] + " ");
            }
            System.out.println();
        }
    }
}