【算法】【Python】二维差分数组与其前缀和（洛谷P3397 地毯）

这个题目我之前其实是做过的，当时使用的是C语言暴力模拟，居然没有TLE，代码如下：

#include <stdio.h>
int a[1000][1000]={0};
int main(){
	int n,m;
	int x1,x2,y1,y2;
	scanf("%d %d",&n,&m);
	while(m--){
		scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
		x1--;x2--;y1--;y2--;
		for (int i=x1;i<=x2;i++){
			for (int j=y1;j<=y2;j++){
				a[i][j]++;
			}
		}
	}
	for (int i=0;i<n;i++){
		for (int j=0;j<n;j++){
			printf("%d ",a[i][j]);
		}
		printf("\n");
	}
}

现在备赛蓝桥杯复习差分与前缀和时二次刷到了这个题目，看了当年用C写的代码根本没用到这个知识点，遍用Python又写了一遍：

n, m = map(int, input().strip().split())
data = [[0] * (n + 1) for _ in range(n + 1)]

for _ in range(m):
    x1, y1, x2, y2 = map(int, input().strip().split())
    data[x1-1][y1-1] += 1  # 左上角 +1
    if x2 < n:
        data[x2][y1-1] -= 1  # 下面一行 -1
    if y2 < n:
        data[x1-1][y2] -= 1  # 右侧一列 -1
    if x2 < n and y2 < n:
        data[x2][y2] += 1  # 右下角 +1

# 计算前缀和
for i in range(n):
    for j in range(1, n):
        data[i][j] += data[i][j-1]

for j in range(n):
    for i in range(1, n):
        data[i][j] += data[i-1][j]

for i in range(n):
    print(" ".join(map(str, data[i][:n])))

二维差分数组与其前缀和的关键（我自己认为的）是在使用二维差分数组时，矩形的右下角（x2, y2）需要进行特殊处理，以确保整个地毯的范围正确地更新。

对于矩形 (x1, y1, x2, y2)：

1. 左上角 (x1, y1) 加 1：表示这个矩形的开始。
2. 右下角的右下 (x2+1, y2+1) 减 1：确保在这个点之后不受影响。
3. 右侧 (x2+1, y1) 减 1：避免额外的列累加。
4. 下侧 (x1, y2+1) 减 1：避免额外的行累加。

下面是一维查分与前缀和的模板：

【差分与前缀和】Python模板

1年前

013810