算法1

利用差分简化操作复杂度

$O(n^2)$

python 代码

def insert(x1,y1,x2,y2,c):
    global b
    b[x1][y1] += c
    b[x2+1][y1] -= c
    b[x1][y2+1] -= c
    b[x2+1][y2+1] += c


if __name__=="__main__":
    n,m,q=[int(i) for i in input().split()]
    a = []
    for _ in range(n):
        a.append([int(i) for i in input().split()])
    #1、求a的差分矩阵b    
    b = [[0]*(m+1) for i in range(n+1)]
    for i in range(n):
        for j in range(m):
            insert(i,j,i,j,a[i][j])
    # 2、对a的区间加法——对b的区间定点加减法
    for _ in range(q):
        x1,y1,x2,y2,c = [int(i) for i in input().split()]
        insert(x1-1,y1-1,x2-1,y2-1,c) 
    # 3、完成所有操作后，求答案b的前缀和矩阵a
    #求前缀和矩阵a
    for i in range(n):
        for j in range(m):
            if i==0 and j==0:
                continue
            elif i==0 and j != 0:
                b[i][j] += b[i][j-1]
            elif i != 0 and j==0:
                b[i][j] += b[i-1][j]
            else:
                b[i][j] += b[i-1][j]+b[i][j-1]-b[i-1][j-1]
    for i in b[:-1]:
        print(' '.join(map(str,i[:-1])))