二维差分算法详解

牛客测试链接

二维差分模板

问题描述

给定一个n行m列的矩阵，下标从1开始。接下来有q次操作，每次操作输入5个参数x1, y1, x2, y2, k，表示把以(x1, y1)为左上角,(x2,y2)为右下角的子矩阵的每个元素都加上k。请输出操作后的矩阵。

输入描述

第一行包含三个整数n,m,q。接下来n行，每行m个整数，代表矩阵的元素。接下来q行，每行5个整数x1, y1, x2, y2, k，分别代表这次操作的参数。

输出描述

输出n行，每行m个数，每个数用空格分开，表示这个矩阵。

算法思路

二维差分算法是一种用于解决矩阵区间更新问题的高效算法。它通过预处理和差分数组的方式，将区间更新的时间复杂度从O(nm)降低到O(1)。

具体步骤如下：

1. 定义一个大小为(n+1)*(m+1)的差分数组diff，用于存储每个位置的差分值。
2. 遍历矩阵的每个元素，将其加到差分数组对应位置上。
3. 对差分数组进行预处理，计算每个位置的前缀和，即diff[i][j]表示原矩阵中(1,1)到(i,j)位置的元素和。
4. 对每次操作，将对应区间的四个角的差分值进行更新，即diff[a][b] += k, diff[c+1][d+1] += k, diff[c+1][b] -= k, diff[a][d+1] -= k。
5. 对差分数组进行再次预处理，计算每个位置的前缀和，即diff[i][j]表示操作后的矩阵中(1,1)到(i,j)位置的元素和。
6. 输出操作后的矩阵。

代码实现

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

public class Main {
    static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
    static StreamTokenizer sr = new StreamTokenizer(in);
    static int MAXN = 1005;
    static int n, m, q;
    static long[][] diff = new long[MAXN][MAXN];
    
    static void build() {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                diff[i][j] += diff[i - 1][j] + diff[i][j - 1] - diff[i - 1][j - 1];
            }
        }
    }
    
    static void clear() {
        for (int i = 1; i <= n + 1; i++) {
            for (int j = 1; j <= m + 1; j++) {
                diff[i][j] = 0;
            }
        }
    }
    
    static void add(int a, int b, int c, int d, int k) {
        diff[a][b] += k;
        diff[c + 1][d + 1] += k;
        diff[c + 1][b] -= k;
        diff[a][d + 1] -= k;
    }
    
    static int nextInt() throws IOException {
        sr.nextToken();
        return (int)sr.nval;
    }
    
    public static void main(String[] args) throws IOException {
        n = nextInt();
        m = nextInt();
        q = nextInt();
        
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                add(i, j, i, j, nextInt());
            }
        }
        
        while (q-- > 0) {
            int a = nextInt();
            int b = nextInt();
            int c = nextInt();
            int d = nextInt();
            int k = nextInt();
            add(a, b, c, d, k);
        }
        
        build();
        
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                out.print(diff[i][j] + " ");
            }
            out.println();
            out.flush();
        }
        
        clear();
    }
}

总结

二维差分算法是一种高效解决矩阵区间更新问题的算法。通过预处理和差分数组的方式，可以将区间更新的时间复杂度从O(nm)降低到O(1)。在实际应用中，可以大大提高算法的效率。