竞赛.算法

前缀和

一、什么是前缀和

前缀和（Prefix Sum）是一种预处理数组的技巧，核心是用空间换时间，把多次区间求和从 O (n) 降到 O (1)。

二、一维前缀和（最常用）

1. 定义

• 原数组：a[1..n]（下标从 1 开始，方便边界）
• 前缀和数组：pre[0..n]
  • pre[0] = 0（哨兵，避免判断）
  • pre[i] = a[1] + a[2] + ... + a[i]（前 i 项和）

2. 递推公式

pre[i] = pre[i-1] + a[i]

3. 区间和公式
求区间 [l, r] 的和：

sum(l, r) = pre[r] - pre[l-1]

4. 示例

原数组：a = [2, 3, -1, 4]（下标 1~4）前缀和：pre = [0, 2, 5, 4, 8]

• sum(1,3) = pre[3] - pre[0] = 4 - 0 = 4
• sum(2,4) = pre[4] - pre[1] = 8 - 2 = 6

5. 复杂度

• 预处理：O (n)
• 单次查询：O (1)
• 空间：O (n)

三、二维前缀和（矩阵）

用于快速求子矩阵和。

1. 定义

• 矩阵：a[1..n][1..m]
• 二维前缀和：pre[i][j]= 左上角 (1,1) 到 (i,j) 的子矩阵和

2. 构建公式

pre[i][j] = pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1] + a[i][j]

3. 子矩阵和公式

求左上角 (x1,y1) 到右下角 (x2,y2) 的和：

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

四、常见应用

• 多次区间和查询
• 子数组和为 k 的个数
• 最大子数组和（结合动态规划）
• 二维矩阵区域和快速查询

补充：数组全局变量的时候在启动程序时全部都会被初始化为0.