当前位置：首页 > news >正文

二维差分算法详解

news 来源：原创 2024/5/20 4:29:40

牛客测试链接

二维差分模板

问题描述

给定一个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)。

具体步骤如下：

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

代码实现

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();}
}