【模板】二维差分

思路

这题是二维前缀和的"逆操作"。二维前缀和解决的是多次查询子矩阵和，而二维差分解决的是多次给子矩阵加值。

先想暴力：每次操作都遍历子矩阵把每个元素加上 c，单次操作 $O(n \times m)$ ，q 次就是 $O(q \times n \times m)$ ，肯定超时。

回忆一维差分是怎么做的：给区间 [l, r] 加 c，只需要 d[l] += c, d[r+1] -= c，最后对差分数组求前缀和就能还原。核心思想是修改 O(1)，最后统一还原。

二维也一样。我们构造一个差分数组 d[i][j]，使得对 d 做二维前缀和之后能还原出原始矩阵 a。

怎么从原矩阵构造差分数组？

既然二维前缀和的公式是：

$ $s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + a[i][j]$ $

那反过来，差分数组就是：

$ $d[i][j] = a[i][j] - a[i-1][j] - a[i][j-1] + a[i-1][j-1]$ $

怎么对子矩阵 (r1,c1) 到 (r2,c2) 加 c？

和一维差分类似，用容斥在四个角打标记：

$ $d[r_1][c_1] \mathrel{+}= c$ $

$ $d[r_2+1][c_1] \mathrel{-}= c$ $

$ $d[r_1][c_2+1] \mathrel{-}= c$ $

$ $d[r_2+1][c_2+1] \mathrel{+}= c$ $

画个图理解：我们在左上角加 c，但这会影响到右边和下面不该加的区域，所以在右边和下面各减掉，而右下角被减了两次要加回来——还是容斥原理。

所有操作打完标记后，对 d 做一次二维前缀和，就得到最终矩阵了。

整个流程：构造差分 $O(n \times m)$ + 打标记 $O(q)$ + 还原 $O(n \times m)$ ，非常高效。

代码

C++
Java
Python3
JavaScript

#include <cstdio>
using namespace std;

static long long a[1005][1005], d[1005][1005];

int main(){
    int n, m, q;
    scanf("%d%d%d", &n, &m, &q);
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            scanf("%lld", &a[i][j]);

    // 构造二维差分数组
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            d[i][j] = a[i][j] - a[i-1][j] - a[i][j-1] + a[i-1][j-1];

    // 处理每次操作，在差分数组上打标记
    while(q--){
        int r1, c1, r2, c2;
        long long c;
        scanf("%d%d%d%d%lld", &r1, &c1, &r2, &c2, &c);
        d[r1][c1] += c;
        d[r2+1][c1] -= c;
        d[r1][c2+1] -= c;
        d[r2+1][c2+1] += c;
    }

    // 对差分数组求二维前缀和，还原最终矩阵
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            d[i][j] += d[i-1][j] + d[i][j-1] - d[i-1][j-1];

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if(j > 1) putchar(' ');
            printf("%lld", d[i][j]);
        }
        putchar('\n');
    }
    return 0;
}

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StreamTokenizer st = new StreamTokenizer(br);
        StringBuilder sb = new StringBuilder();

        st.nextToken(); int n = (int)st.nval;
        st.nextToken(); int m = (int)st.nval;
        st.nextToken(); int q = (int)st.nval;

        long[][] a = new long[n+2][m+2];
        long[][] d = new long[n+2][m+2];

        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= m; j++){
                st.nextToken();
                a[i][j] = (long)st.nval;
            }

        // 构造二维差分数组
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= m; j++)
                d[i][j] = a[i][j] - a[i-1][j] - a[i][j-1] + a[i-1][j-1];

        // 处理每次操作
        for(int k = 0; k < q; k++){
            st.nextToken(); int r1 = (int)st.nval;
            st.nextToken(); int c1 = (int)st.nval;
            st.nextToken(); int r2 = (int)st.nval;
            st.nextToken(); int c2 = (int)st.nval;
            st.nextToken(); long c = (long)st.nval;
            d[r1][c1] += c;
            d[r2+1][c1] -= c;
            d[r1][c2+1] -= c;
            d[r2+1][c2+1] += c;
        }

        // 二维前缀和还原
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= m; j++)
                d[i][j] += d[i-1][j] + d[i][j-1] - d[i-1][j-1];

        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m; j++){
                if(j > 1) sb.append(' ');
                sb.append(d[i][j]);
            }
            sb.append('\n');
        }
        System.out.print(sb);
    }
}

import sys
input = sys.stdin.readline

def main():
    n, m, q = map(int, input().split())
    a = [[0]*(m+2) for _ in range(n+2)]
    d = [[0]*(m+2) for _ in range(n+2)]
    for i in range(1, n+1):
        row = list(map(int, input().split()))
        for j in range(1, m+1):
            a[i][j] = row[j-1]
    for i in range(1, n+1):
        for j in range(1, m+1):
            d[i][j] = a[i][j] - a[i-1][j] - a[i][j-1] + a[i-1][j-1]
    for _ in range(q):
        parts = list(map(int, input().split()))
        r1, c1, r2, c2, c = parts
        d[r1][c1] += c
        d[r2+1][c1] -= c
        d[r1][c2+1] -= c
        d[r2+1][c2+1] += c
    for i in range(1, n+1):
        for j in range(1, m+1):
            d[i][j] += d[i-1][j] + d[i][j-1] - d[i-1][j-1]
    out = []
    for i in range(1, n+1):
        out.append(' '.join(str(d[i][j]) for j in range(1, m+1)))
    sys.stdout.write('\n'.join(out) + '\n')

main()

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', line => lines.push(line));
rl.on('close', () => {
    let idx = 0;
    const [n, m, q] = lines[idx++].split(' ').map(Number);
    const a = Array.from({length: n+2}, () => new Array(m+2).fill(0));
    const d = Array.from({length: n+2}, () => new Array(m+2).fill(0));
    for (let i = 1; i <= n; i++) {
        const row = lines[idx++].split(' ').map(Number);
        for (let j = 1; j <= m; j++) {
            a[i][j] = row[j-1];
        }
    }
    for (let i = 1; i <= n; i++)
        for (let j = 1; j <= m; j++)
            d[i][j] = a[i][j] - a[i-1][j] - a[i][j-1] + a[i-1][j-1];
    for (let k = 0; k < q; k++) {
        const parts = lines[idx++].split(' ').map(Number);
        const [r1, c1, r2, c2, c] = parts;
        d[r1][c1] += c;
        d[r2+1][c1] -= c;
        d[r1][c2+1] -= c;
        d[r2+1][c2+1] += c;
    }
    for (let i = 1; i <= n; i++)
        for (let j = 1; j <= m; j++)
            d[i][j] += d[i-1][j] + d[i][j-1] - d[i-1][j-1];
    const out = [];
    for (let i = 1; i <= n; i++) {
        const row = [];
        for (let j = 1; j <= m; j++) row.push(d[i][j]);
        out.push(row.join(' '));
    }
    console.log(out.join('\n'));
});

复杂度

时间复杂度： $O(n \times m + q)$ 。构造差分和还原各遍历一次矩阵，每次操作 $O(1)$ 。
空间复杂度： $O(n \times m)$ 。存储差分数组。

题解 | #【模板】二维差分#

【模板】二维差分

思路

代码

复杂度