Acwing 798.差分矩阵

作用

• 让前缀和矩阵a中的子矩阵区域中每个元素加上一个c
• 等价为在差分矩阵b中[x1, y1]元素上加c，使得a中[x1, y1]右上角区域所有元素加c，故需要打补丁，如下

b[x1][y1] += c
b[x2 + 1][y1] -= c
b[x1][y2 + 1] -= c
b[x2 + 1][y2 + 1] += c # 这个区域被减去两次，故要加回来

构造方法

• 构造同一维差分
• 假想a数组为空，那么b数组一开始也为空，但实际上a数组并不为空，因此需要在[i, j]和[i, j]范围内加上a[i][j]，就构造出了差分数组b了

题解

N = 1010
a = [[0] * N for _ in range(N)]
b = [[0] * N for _ in range(N)]


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


def main():
    n, m, q = map(int, input().split(' '))

    for i in range(1, n + 1):
        a[i][1: m+1] = list(map(int, input().split(' ')))

    # 构造差分矩阵b
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            insert(i, j, i, j, a[i][j])

    while q:
        q -= 1
        x1, y1, x2, y2, c = map(int, input().split(' '))
        insert(x1, y1, x2, y2, c) # 对这个子区域中每个元素加c

    # 对差分矩阵b求一次前缀和得到q个操作之后的a数组
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            a[i][j] = a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1] + b[i][j]
            print(a[i][j], end=' ')
        print()

main()