一维差分
差分就是数组前面的一个元素减去后面的一个元素所得到的一个含义为两元素差值的数组
while True:try:n,m=map(int,input().split())a=list(map(int,input().split()))diff=[0]*(n+1)###防止尾出错diff[0]=a[0]for i in range(1,n):diff[i]=a[i]-a[i-1]for _ in range(m):x,y,z=map(int,input().split())x=x-1y=y-1diff[x]+=zdiff[y+1]-=za[0]=diff[0]###这个很重要，防止头出错for i in range(1,n):a[i]=a[i-1]+diff[i]print(" ".join(map(str,a)))except:break
二维差分
diff(i,j)=a(i,j)-a(i-1,j)-a(i,j-1)+a(i-1,j-1) (即sum替换成a a替换成diff)
n,m=map(int,input().split())
a=[[0]*(m+1) for i in range(n+1)]
diff=[[0]*(m+1) for i in range(n+1)]
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):diff[i][j]=a[i][j]-a[i-1][j]-a[i][j-1]+a[i-1][j-1]
def print_matrix(matrix, name):"""辅助函数：打印矩阵"""print(f"--- {name} ---")for row in matrix:print("\t".join(map(str, row)))print()# 1. 初始化原始矩阵 a (图中的左上角矩阵)
# 注意：为了方便对应图中的坐标 (1,1) 开始，我们在外面包一圈 0
# 实际数据从索引 1 开始
a = [[0, 0, 0, 0, 0],[0, 1, 2, 3, 4],[0, 5, 6, 7, 8],[0, 9, 10, 11, 12],[0, 13, 14, 15, 16]
]n = 4 # 矩阵大小 4x4# 2. 构建差分数组 diff (图中的右上角矩阵)
# 差分数组的定义：diff[i][j] = a[i][j] - a[i-1][j] - a[i][j-1] + a[i-1][j-1]
diff = [[0] * (n + 1) for _ in range(n + 1)]for i in range(1, n + 1):for j in range(1, n + 1):diff[i][j] = a[i][j] - a[i-1][j] - a[i][j-1] + a[i-1][j-1]print("初始 diff 矩阵:")
print_matrix(diff, "diff")# 3. 核心操作：在子矩阵 (x1, y1) 到 (x2, y2) 增加 val
# 图中是：从 (2,2) 到 (3,3) 增加 3
x1, y1 = 2, 2
x2, y2 = 3, 3
val = 3def update_diff(diff, x1, y1, x2, y2, val):"""二维差分数组更新公式"""diff[x1][y1] += val # 左上角 +valdiff[x2 + 1][y2 + 1] += val # 右下角 +val (抵消多加的)diff[x1][y2 + 1] -= val # 右上角 -val (消除影响)diff[x2 + 1][y1] -= val # 左下角 -val (消除影响)update_diff(diff, x1, y1, x2, y2, val)print(f"更新操作：区域 ({x1},{y1}) 到 ({x2},{y2}) 增加 {val}")
print_matrix(diff, "更新后的 diff (对应图中右下角)")# 4. 还原矩阵 (求二维前缀和)
# 通过 diff 还原出新的 a
new_a = [[0] * (n + 1) for _ in range(n + 1)]for i in range(1, n + 1):for j in range(1, n + 1):# 前缀和公式：当前值 = 上 + 左 - 左上 + 差分new_a[i][j] = new_a[i-1][j] + new_a[i][j-1] - new_a[i-1][j-1] + diff[i][j]print("最终还原的矩阵 a (对应图中左下角):")
print_matrix(new_a, "new_a")# 验证结果 (打印不带外围0的部分)
print("结果验证 (仅数据部分):")
for i in range(1, n + 1):print([new_a[i][j] for j in range(1, n + 1)])