三种语言实现二维差分（C++/Python/Java)

题目

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

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

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

输入格式

第一行包含整数 n,m,q

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

接下来 q 行，每行包含 5 个整数 x1,y1,x2,y2,c表示一个操作。

输出格式

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

数据范围

1≤n,m≤1000
1≤q≤100000
1≤x1≤x2≤n
1≤y1≤y2≤m
−1000≤c≤1000
−1000≤矩阵内元素的值≤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

C++

#include <bits/stdc++.h>
 
using namespace std;
 
const int N = 1010;
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()
{
    int n,m,q;
    cin >> n >> m >> q;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
        {
            cin >> a[i][j];
            insert(i,j,i,j,a[i][j]);
        }
    
        
    while(q--)
    {
        int x1, y1, x2, y2, c;
        cin >> 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++)
        {
            a[i][j] = b[i][j] + a[i-1][j] + a[i][j-1] - a[i-1][j-1];
            cout << a[i][j] << " ";
        }
        cout << endl;
    }
        
}

Python

N = 1010
a = [[0] * N for _ in range(N)]
b = [[0] * N for _ in range(N)]
 
n, m, q = map(int, input().split())

def insert(x1,y1,x2,y2,c):
    b[x1][y1] += c
    b[x2+1][y1] -= c
    b[x1][y2+1] -= c
    b[x2+1][y2+1] += c
 
for i in range(1, n+1):
    a[i] = [0] + list(map(int, input().split()))
 
for i in range(1, n+1):
    for j in range(1, m+1):
        insert(i,j,i,j,a[i][j])
 
while q:
    x1,y1,x2,y2,c = map(int,input().split())
    insert(x1,y1,x2,y2,c)
    q -= 1

for i in range(1, n+1):
    for j in range(1, m+1):
        a[i][j] = b[i][j] + a[i-1][j] + a[i][j-1] - a[i-1][j-1]
        print(a[i][j], end=" ")
    print()

Java

import java.util.*;
 
public class Main{
    static int N = 1010;
    static int n, m, q;
    static int[][] b = new int[N][N];
    static int[][] a = new int[N][N];
    
    public static 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;
    }
    
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        q = sc.nextInt();
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= m; j++)
            {
                a[i][j] = sc.nextInt();
                insert(i,j,i,j,a[i][j]);
            }
        
        while(q > 0)
        {
            q -= 1;
            int x1 = sc.nextInt();
            int y1 = sc.nextInt();
            int x2 = sc.nextInt();
            int y2 = sc.nextInt();
            int c = sc.nextInt();
            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][j - 1] + b[i - 1][j] - b[i - 1][j - 1];
                System.out.print(b[i][j] + " ");
            }
            System.out.println();
        }
    }
    
}