蓝桥杯最后十天冲刺day 1

模板：

1.一维前缀和差分 二位前缀和差分

思想：

一维前缀和的核心思想是预处理一个数组 prefix，其中 prefix[i] 表示原数组 arr 前 i 个元素的和（通常 prefix[0] = 0）。通过前缀和，可以快速计算任意区间 [l, r] 的和：sum(l, r) = prefix[r] - prefix[l-1]。

模板：

python

复制

n = len(arr)
prefix = [0] * (n + 1)
for i in range(1, n + 1):
    prefix[i] = prefix[i - 1] + arr[i - 1]

# 查询区间 [l, r] 的和（下标从 0 开始）
def query(l, r):
    return prefix[r + 1] - prefix[l]

对模板的解释：

求prefix【i】使用的递归，

蓝桥杯例题：
 完全模板题

二维：

思想：

二维前缀和用于快速计算矩阵中子矩阵的和。定义 prefix[i][j] 为以 (0,0) 为左上角、(i-1,j-1) 为右下角的子矩阵的和。通过以下公式预处理：

python

prefix[i][j] = prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1] + matrix[i-1][j-1]

查询子矩阵 (x1,y1) 到 (x2,y2) 的和：

sum = prefix[x2+1][y2+1] - prefix[x1][y2+1] - prefix[x2+1][y1] + prefix[x1][y1]

模板：

python

rows, cols = len(matrix), len(matrix[0])
prefix = [[0] * (cols + 1) for _ in range(rows + 1)]
for i in range(1, rows + 1):
    for j in range(1, cols + 1):
        prefix[i][j] = prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1] + matrix[i-1][j-1]

# 查询子矩阵 (x1,y1) 到 (x2,y2) 的和（下标从 0 开始）
def query(x1, y1, x2, y2):
    return prefix[x2+1][y2+1] - prefix[x1][y2+1] - prefix[x2+1][y1] + prefix[x1][y1]

蓝桥杯例题：

小明有一个大小为 N × M 的矩阵，可以理解为一个 N 行 M 列的二维数组。 我们定义一个矩阵 m 的稳定度 f(m) 为 f(m) = max(m) − min(m)，其中 max(m) 表示矩阵 m 中的最大值，min(m) 表示矩阵 m 中的最小值。现在小明想要从这个矩阵中找到一个稳定度不大于 limit 的子矩阵，同时他还希望这个子矩阵的面积越大越好（面积可以理解为矩阵中元素个数）。

子矩阵定义如下：从原矩阵中选择一组连续的行和一组连续的列，这些行列交点上的元素组成的矩阵即为一个子矩阵。 

输入格式

第一行输入两个整数 N，M，表示矩阵的大小。

接下来 N 行，每行输入 M 个整数，表示这个矩阵。

最后一行输入一个整数 limit，表示限制。 

输出格式

输出一个整数，分别表示小明选择的子矩阵的最大面积。 
 

N,M = map(int,input().split())
matrix = []
for i in range(N):
    row = list(map(int,input().split()))
    matrix.append(row)
limit = int(input())
max_area = 0
for x1 in range(N):
    for y1 in range(M):
        for x2 in range(x1,N):
            for y2 in range(y1,M):
                max_number = -float('inf')
                min_number = float('inf')
                for x in range(x1,x2+1):
                    for y in range(y1,y2+1):
                        max_number = max(matrix[x][y],max_number)
                        min_number = min(matrix[x][y],min_number)
                if max_number - min_number <= limit:
                    area = (x2 - x1 + 1) * (y2 - y1 + 1)

                    if area > max_area:
                        max_area = area
print(max_area)

前缀和的应用场景

1. ​频繁区间求和：一维数组区间和或二维矩阵子矩阵和。
2. ​优化暴力枚举：将 O(n²) 或 O(n³) 的枚举优化为 O(n) 或 O(n²)。
3. ​结合其他算法：如滑动窗口、差分、动态规划等。

注意事项

• ​下标处理：前缀和数组通常从 1 开始，原数组从 0 开始。
• ​边界检查：查询时确保区间合法（如 l <= r）。