Python 矩阵操作：子矩阵加值 - 优化时间复杂度

n, m, q = map(int, input().split())
matrix = [list(map(int, input().split())) for _ in range(n)]
operations = [list(map(int, input().split())) for _ in range(q)]

# 创建一个新矩阵，用于存储操作后的结果
new_matrix = [[0] * m for _ in range(n)]

# 遍历每个操作
for op in operations:
    x1, y1, x2, y2, c = op
    # 更新子矩阵中的每个元素
    for i in range(x1 - 1, x2):
        for j in range(y1 - 1, y2):
            new_matrix[i][j] += c

# 输出最终矩阵
for row in new_matrix:
    print(' '.join(map(str, row)))

时间复杂度分析：

遍历每个操作，并更新子矩阵中的每个元素，时间复杂度为 O(qnm)。输出最终矩阵的时间复杂度为 O(nm)。因此，总的时间复杂度为 O(qnm+nm)。

优化思路：

当前代码的时间复杂度较高，主要原因是遍历所有操作时，对每个操作都需要遍历子矩阵中的所有元素进行加值。为了优化时间复杂度，可以采用差分数组的思想，将操作转换为对矩阵边界值的修改，从而将时间复杂度降低到 O(q+n*m)。

差分数组优化代码：

n, m, q = map(int, input().split())
matrix = [list(map(int, input().split())) for _ in range(n)]
operations = [list(map(int, input().split())) for _ in range(q)]

# 创建差分数组
diff = [[0] * (m + 1) for _ in range(n + 1)]

# 将原矩阵转换为差分数组
for i in range(n):
    for j in range(m):
        diff[i + 1][j + 1] = matrix[i][j]
        diff[i + 1][j] -= matrix[i][j]
        diff[i][j + 1] -= matrix[i][j]
        diff[i][j] += matrix[i][j]

# 处理每个操作
for op in operations:
    x1, y1, x2, y2, c = op
    diff[x1][y1] += c
    diff[x2 + 1][y1] -= c
    diff[x1][y2 + 1] -= c
    diff[x2 + 1][y2 + 1] += c

# 将差分数组还原为最终矩阵
for i in range(n):
    for j in range(m):
        matrix[i][j] = diff[i + 1][j + 1]
        matrix[i][j] += diff[i + 1][j]
        matrix[i][j] += diff[i][j + 1]
        matrix[i][j] -= diff[i][j]

# 输出最终矩阵
for row in matrix:
    print(' '.join(map(str, row)))

使用差分数组优化后，时间复杂度降低为 O(q+n*m)，在操作次数较多时可以有效提高程序效率。