下面是关于【前缀和（Prefix Sum）算法】的完整讲解，涵盖原理、应用场景、代码模板及常见变种，适用于蓝桥杯、LeetCode、NOI 等竞赛与实际开发中的高频问题。

📘 目录

  1. 前缀和的定义与原理
  2. 一维前缀和实现与应用
  3. 二维前缀和实现与应用
  4. 差分数组与前缀和的关系
  5. 常见应用场景举例
  6. 面试题/竞赛题精选
  7. 小结与学习建议

1. ✅ 前缀和的定义与原理

前缀和（Prefix Sum）是一种高效处理区间和查询的技巧，预处理一次后可以用 O(1) 的时间求出任意区间的和。

定义：

给定一个数组 a[1..n]，其前缀和数组 s[1..n] 定义如下：s[i]=a[1]+a[2]+⋯+a[i]

则任意区间 [l, r] 的和为：sum[l..r]=s[r]−s[l−1]

2. 📌 一维前缀和实现与应用

💡 代码模板（C++）

int a[N], s[N]; // 原数组 和 前缀和数组
// 构造前缀和
for (int i = 1; i <= n; ++i) {
    s[i] = s[i - 1] + a[i];
}

// 查询区间 [l, r] 的和
int sum = s[r] - s[l - 1];

📌 示例题：求数组中多个区间的和

输入：

a = [1, 2, 3, 4, 5]
q = 3 个查询区间：[1,3], [2,4], [1,5]

处理所有查询只需 O(n + q) 时间，比暴力 O(nq) 高效很多。

3. 🧮 二维前缀和实现与应用

用于高效计算二维矩阵中子矩阵的和。

定义：

设原矩阵为 a[i][j]，二维前缀和 s[i][j] 表示左上角 (1,1) 到 (i,j) 的子矩阵元素和：s[i][j]=a[i][j]+s[i−1][j]+s[i][j−1]−s[i−1][j−1]

区间查询（子矩阵和）公式：

对矩阵中子区域 (x1,y1)到(x2,y2)：sum=s[x2][y2]−s[x1−1][y2]−s[x2][y1−1]+s[x1−1][y1−1]

💡 C++模板：

int a[N][N], s[N][N];
// 构造前缀和
for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= m; ++j)
        s[i][j] = a[i][j] + s[i-1][j] + s[i][j-1] - s[i-1][j-1];

// 查询子矩阵和
int sum = s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1];

4. 🔁 差分数组与前缀和的关系

差分（Difference）数组是前缀和的“逆运算”，常用于批量修改区间。

  • 差分数组 d[i] = a[i] - a[i-1]
  • 恢复原数组：a[i] = d[1] + d[2] + ... + d[i] = 前缀和

差分用于快速更新、前缀和用于快速查询。

5. 🧩 常见应用场景

应用场景方法
区间求和（1D/2D）前缀和
多个区间快速求和前缀和
子矩阵和（如热力图求和）二维前缀和
区间频次统计（频率计数）差分 + 前缀和
前缀/后缀最大值问题配合前缀最值数组

6. 🎯 面试题 / 竞赛题精选

题目平台
LeetCode 303. 区域和检索 – 数组不可变LeetCode
LeetCode 304. 二维区域和检索LeetCode
洛谷 P1919 区间和洛谷
[蓝桥杯真题：矩阵区域查询]（需要二维前缀和）蓝桥杯

7. 📌 小结与学习建议

  • 前缀和能将 O(n) 查询优化为 O(1)；
  • 二维前缀和适用于图像处理、热力图分析、子矩阵累加等场景；
  • 差分数组与前缀和可以结合使用，提升区间修改 + 查询效率；
  • 编程竞赛中是非常高频的技巧，必须熟练掌握模板及原理。