一维差分
三个步骤
一、将原矩阵内的所有数值全部当作零
二、写出差分的公式
## b为构建的差分矩阵,长度为[n + 2,n + 2]
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
三、把原矩阵数据插入
代码
n, m, q = map(int,input().split())
ll = [None] * (n + 1)
ll[0] = [0] * (m + 1)
for i in range(1, n + 1):
ll[i] = list(map(int,('0 ' + input()).split()))
b = [[0] * (m + 2) for i in range(n + 2)]
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):
for j in range(1, m + 1):
insert(i, j, i ,j , ll[i][j])
while q:
q -= 1
x1, y1, x2, y2, c = map(int,input().split())
insert(x1, y1, x2, y2, c)
for i in range(1, n + 1):
for j in range(1, m + 1):
b[i][j] += b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1]
print(b[i][j], end=' ')
print()