二维差分

一、算法思想

相比于 一维差分，二维差分考虑的是差分矩阵的前缀和为原矩阵。

同样的，考虑对 $A$ 矩阵中，左上角坐标 $(x_1,y_1)$、右下角坐标 $(x_2,y_2)$ 的子矩阵内的元素加上 $c$。那么可以通过对差分矩阵 $B$ 在 $O(1)$ 的时间内完成，如下：

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

二、算法模板

Go

type Difference2D struct {
    diff [][]int
    n, m int
}

// NewDifference2D 初始化二维差分数组
func NewDifference2D(n, m int) *Difference2D {
    diff := make([][]int, n+2)
    for i := range diff {
        diff[i] = make([]int, m+2)
    }
    return &Difference2D{
        diff: diff,
        n:    n,
        m:    m,
    }
}

// 给子矩阵内的元素加上 c
// 子矩阵的左上角和右下角坐标为 (x1, y1) 和 (x2, y2)
func (df *Difference2D) insert(x1, y1, x2, y2, c int) {
    df.diff[x1][y1] += c
    df.diff[x2+1][y1] -= c
    df.diff[x1][y2+1] -= c
    df.diff[x2+1][y2+1] += c
}

// 获取最终矩阵
func (df *Difference2D) final() (ans [][]int) {
    ans = make([][]int, df.n+1)
    for i := range ans {
        ans[i] = make([]int, df.m+1)
        for j := range ans[i] {
            ans[i][j] = df.diff[i][j]
        }
    }
    for i := 1; i <= df.n; i++ {
        for j := 1; j <= df.m; j++ {
            ans[i][j] += ans[i-1][j] + ans[i][j-1] - ans[i-1][j-1]
        }
    }
    for i := range ans {
        ans[i] = ans[i][1:]
    }
    ans = ans[1:]
    return
}

三、代码实战

AcWing 0798

---

题目：差分矩阵

输入一个 $n$ 行 $m$ 列的整数矩阵，再输入 $q$ 个操作，每个操作包含五个整数 $x_1,y_1,x_2,y_2,c$，其中 $(x1,y1)$ 和 $(x2,y2)$ 表示一个子矩阵的左上角坐标和右下角坐标。

每个操作都要将选中的子矩阵中的每个元素的值加上 $c$。

请你将进行完所有操作后的矩阵输出。

输入格式

第一行包含三个整数 $n$，$m$，$q$。

接下来 $n$ 行，每行包含 $m$ 个整数，表示整数矩阵。

接下来 $q$ 行，每行包含五个整数 $x_1,y_1,x_2,y_2,c$，表示一个操作。

输出格式

共 $n$ 行，每行 $m$ 个整数，表示所有操作进行完毕后的最终矩阵。

数据范围

$1 \le n,m \le 1000$

$1 \le q \le 2 \times 10^5$

$1 \le x_1 \le x_2 \le n$

$1 \le y_1 \le y_2 \le m$

$-1000 \le c \le 1000$

$-1000 \le \text{矩阵内元素的值} \le 1000$

输入样例：

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

输出样例：

2 3 4 1

4 3 4 1

2 2 2 2

解答代码：

#include <iostream>

using namespace std;

const int N = 1010;

int n, m, q;
int a[N][N], b[N][N];

void insert(int x1, int y1, int x2, int y2, int c)
{
    b[x1][y1] += c;
    b[x2 + 1][y1] -= c;
    b[x1][y2 + 1] -= c;
    b[x2 + 1][y2 + 1] += c;
}

int main()
{
    scanf("%d%d%d", &n, &m, &q);

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            scanf("%d", &a[i][j]);
            insert(i, j, i, j, a[i][j]);
        }
    }
    
    while (q--) {
        int x1, y1, x2, y2, c;
        scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &c);
        insert(x1, y1, x2, y2, c);
    }
    
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            b[i][j] += b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1];
            printf("%d ", b[i][j]);
        }
        printf("\n");
    }

    return 0;
}

package main

import (
    "bufio"
    . "fmt"
    "io"
    "os"
)

type Difference2D struct {
    diff [][]int
    n, m int
}

// NewDifference2D 初始化二维差分数组
func NewDifference2D(n, m int) *Difference2D {
    diff := make([][]int, n+2)
    for i := range diff {
        diff[i] = make([]int, m+2)
    }
    return &Difference2D{
        diff: diff,
        n:    n,
        m:    m,
    }
}

// 给子矩阵内的元素加上 c
// 子矩阵的左上角和右下角坐标为 (x1, y1) 和 (x2, y2)
func (df *Difference2D) insert(x1, y1, x2, y2, c int) {
    df.diff[x1][y1] += c
    df.diff[x2+1][y1] -= c
    df.diff[x1][y2+1] -= c
    df.diff[x2+1][y2+1] += c
}

// 获取最终矩阵
func (df *Difference2D) final() (ans [][]int) {
    ans = make([][]int, df.n+1)
    for i := range ans {
        ans[i] = make([]int, df.m+1)
        for j := range ans[i] {
            ans[i][j] = df.diff[i][j]
        }
    }
    for i := 1; i <= df.n; i++ {
        for j := 1; j <= df.m; j++ {
            ans[i][j] += ans[i-1][j] + ans[i][j-1] - ans[i-1][j-1]
        }
    }
    for i := range ans {
        ans[i] = ans[i][1:]
    }
    ans = ans[1:]
    return
}

func run(_r io.Reader, out io.Writer) {
    in := bufio.NewReader(_r)

    var n, m, k int
    Fscan(in, &n, &m, &k)

    df := NewDifference2D(n, m)

    var x int
    for i := 0; i < n; i++ {
        for j := 0; j < m; j++ {
            Fscan(in, &x)
            df.insert(i+1, j+1, i+1, j+1, x)
        }
    }

    for i := 0; i < k; i++ {
        var x1, y1, x2, y2, c int
        Fscan(in, &x1, &y1, &x2, &y2, &c)
        df.insert(x1, y1, x2, y2, c)
    }

    ans := df.final()

    for i := 0; i < n; i++ {
        for j := 0; j < m; j++ {
            Fprintf(out, "%d ", ans[i][j])
        }
        Fprintf(out, "\n")
    }
}

func main() {
    run(os.Stdin, os.Stdout)
}