前缀和：原理、图解与 C++ 实战

一、什么是前缀和

前缀和（Prefix Sum）是一种典型的"空间换时间"预处理技巧：先构造一个数组 prefix，让 prefix[i] 等于原数组前 i 个元素之和。之后任意区间的和都能用两次前缀和做差得到，单次查询 O(1)。

一句话定义
前缀和 = 预先算好"前 i 项之和"，用做差把区间求和从 O(n) 降到 O(1)。

它的典型应用场景是"多次询问某区间的累计值"。如果每次询问都从左到右扫一遍，单次 O(n)，m 次询问共 O(mn)；用前缀和后变成 O(n + m)，差异极大。

1.1 一维与二维

维度	预处理	查询	空间
一维前缀和	prefix[i] = prefix[i-1] + nums[i-1]	sum[l..r] = prefix[r+1] - prefix[l]	O(n)
二维前缀和	容斥原理递推	子矩阵面积做差	O(nm)

⚠ 下标约定
本文统一采用"prefix 数组下标从 1 开始"的写法：prefix[0] = 0，prefix[i] 表示原数组前 i 项之和。这样查询区间 [l, r]（原数组下标）的和时直接用 prefix[r+1] - prefix[l]，避免 l == 0 时越界的特判。这是面试题里最常用也最不易写错的写法。

二、核心原理与图解

理解前缀和的关键，是理解"做差即区间和"这个核心恒等式。下面三张图分别展示一维构造、区间求和、二维矩阵的构造与查询。

2.1 一维前缀和构造图

以原数组 [3, 1, 4, 1, 5, 9] 为例，逐项累加得到 prefix 数组。

图 1：一维前缀和数组的构造过程

2.2 区间求和过程图

构造完成后，sum[l..r] = prefix[r+1] - prefix[l]。下面演示求区间 [2, 4]（原数组下标）即 [4, 1, 5] 的和。

图 2：用 prefix 做差求任意区间和

2.3 二维前缀和矩阵图

二维前缀和 S[i][j] 表示"原矩阵中以 (0,0) 为左上角、(i-1,j-1) 为右下角的子矩阵元素之和"。构造用容斥原理，查询同理。

图 3：二维前缀和容斥原理——构造与查询

2.4 复杂度分析

⏱ 时间复杂度
预处理 O(n)（一维）或 O(nm)（二维）；每次查询 O(1)。若 m 次询问，总复杂度 O(n + m)。

💾 空间复杂度
O(n)（一维）或 O(nm)（二维）。空间换时间的典型代表。

三、通用模板

前缀和的代码非常短，关键在"下标 +1 偏移"和"做差方向"。下面给出两种最常见模板。

3.1 一维前缀和模板

// 一维前缀和通用模板
vector<int> buildPrefix(const vector<int>& nums) {
    int n = (int)nums.size();
    vector<int> prefix(n + 1, 0);  // prefix[0] = 0 是哨兵
    for (int i = 1; i <= n; ++i) {
        prefix[i] = prefix[i - 1] + nums[i - 1];
    }
    return prefix;
}

// 查询区间 [l, r]（原数组下标，闭区间）之和，O(1)
int rangeSum(const vector<int>& prefix, int l, int r) {
    return prefix[r + 1] - prefix[l];
}

一维模板三要点
1. prefix 长度 n+1，下标 1~n——多出一个哨兵 prefix[0]=0
2. 构造公式：prefix[i] = prefix[i-1] + nums[i-1]，注意 nums 下标减一
3. 查询公式：prefix[r+1] - prefix[l]，r 要 +1

3.2 二维前缀和模板

// 二维前缀和通用模板
vector<vector<int>> buildPrefix2D(const vector<vector<int>>& mat) {
    int n = (int)mat.size(), m = (int)mat[0].size();
    vector<vector<int>> S(n + 1, vector<int>(m + 1, 0));
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            // 容斥：左 + 上 - 左上 + 当前
            S[i][j] = mat[i - 1][j - 1]
                    + S[i - 1][j]
                    + S[i][j - 1]
                    - S[i - 1][j - 1];
        }
    }
    return S;
}

// 查询左上 (r1,c1) 到右下 (r2,c2) 子矩阵之和，闭区间
int regionSum(const vector<vector<int>>& S,
                 int r1, int c1, int r2, int c2) {
    return S[r2 + 1][c2 + 1]
         - S[r1][c2 + 1]
         - S[r2 + 1][c1]
         + S[r1][c1];
}

二维模板三要点
1. S 多一行一列做哨兵——避免 i-1、j-1 越界
2. 构造公式"加左加上减左上加自身"——容斥核心
3. 查询公式"右下减上减左加左上"——左上角被减两次要加回

四、示例一：一维区间和

题目：给定数组 nums = [3, 1, 4, 1, 5, 9, 2, 6]，回答 m 次询问，每次给出 [l, r] 求该闭区间的元素之和。

4.1 示例

构造 prefix = [0, 3, 4, 8, 9, 14, 23, 25, 31]
询问 [2, 5]：答案 = prefix[6] - prefix[2] = 23 - 4 = 19（对应 4+1+5+9=19）
询问 [0, 7]：答案 = prefix[8] - prefix[0] = 31 - 0 = 31（即整个数组之和）

图 4：一维区间和查询——哨兵让公式统一

4.2 C++ 代码

#include <vector>
#include <iostream>
using namespace std;

int main() {
    vector<int> nums = {3, 1, 4, 1, 5, 9, 2, 6};
    int n = (int)nums.size();

    // 1. 预处理前缀和
    vector<int> prefix(n + 1, 0);
    for (int i = 1; i <= n; ++i) {
        prefix[i] = prefix[i - 1] + nums[i - 1];
    }

    // 2. 处理 m 次询问
    int m; cin >> m;
    while (m--) {
        int l, r; cin >> l >> r;     // 闭区间 [l, r]
        cout << prefix[r + 1] - prefix[l] << '\n';
    }
    return 0;
}

核心就两行：构造时 prefix[i] = prefix[i-1] + nums[i-1]，查询时 prefix[r+1] - prefix[l]。再多的询问都只需 O(1)。

五、示例二：二维子矩阵和

题目（LeetCode 304）：给定一个二维矩阵 matrix，实现 sumRegion(r1, c1, r2, c2) 方法，返回左上角 (r1, c1) 到右下角 (r2, c2) 子矩阵的元素之和。

5.1 示例

矩阵：

查询 sumRegion(2, 1, 4, 3) 应返回 8（左上 (2,1) 到右下 (4,3) 的子矩阵 = 2+0+1+1+0+1+0+3+0 = 8）。

图 5：二维子矩阵和——查询 (2,1)→(4,3) 的子矩阵

5.2 C++ 代码

#include <vector>
using namespace std;

class NumMatrix {
private:
    vector<vector<int>> S;  // 二维前缀和

public:
    NumMatrix(const vector<vector<int>>& matrix) {
        int n = (int)matrix.size(), m = n ? (int)matrix[0].size() : 0;
        S.assign(n + 1, vector<int>(m + 1, 0));
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j) {
                // 容斥：自身 + 上 + 左 - 左上（左上加重复）
                S[i][j] = matrix[i - 1][j - 1]
                        + S[i - 1][j]
                        + S[i][j - 1]
                        - S[i - 1][j - 1];
            }
        }
    }

    int sumRegion(int r1, int c1, int r2, int c2) {
        // 容斥：右下 - 上 - 左 + 左上（左上减两次要加回）
        return S[r2 + 1][c2 + 1]
             - S[r1][c2 + 1]
             - S[r2 + 1][c1]
             + S[r1][c1];
    }
};

💡 容斥记忆法
构造："自 + 上 + 左 − 左上"（左上角被算了两次，减一次）
查询："右下 − 上 − 左 + 左上"（左上角被减了两次，加一次）
两套公式恰好是"加加减"的镜像关系，便于对照记忆。

六、示例三：和为 K 的子数组

题目（LeetCode 560）：给定数组 nums 和整数 k，统计数组中和为 k 的连续子数组个数。

6.1 思路：前缀和 + 哈希

子数组 nums[i..j] 的和 = prefix[j+1] - prefix[i]。要求 prefix[j+1] - prefix[i] == k，即对每个 j，找有多少个 i 满足 prefix[i] == prefix[j+1] - k。

用哈希表记录已经见过的每种前缀和值出现的次数，每遍历到一个新的前缀和 sum，答案累加 cnt[sum - k]。

图 6：前缀和 + 哈希表统计和为 k 的子数组

6.2 C++ 代码

#include <vector>
#include <unordered_map>
using namespace std;

int subarraySum(const vector<int>& nums, int k) {
    unordered_map<int, int> cnt;  // 前缀和值 → 出现次数
    cnt[0] = 1;                  // 哨兵：空前缀和=0 出现 1 次
    int sum = 0, ans = 0;
    for (int x : nums) {
        sum += x;                // 滚动前缀和，省去 prefix 数组
        // 找有多少个前缀和等于 sum - k
        if (cnt.count(sum - k)) {
            ans += cnt[sum - k];
        }
        cnt[sum]++;              // 当前前缀和入表
    }
    return ans;
}

💡 三个关键细节
1. 哨兵 cnt[0] = 1——处理"以第 0 个元素开头"的子数组，避免特判
2. 先查再加——顺序不能反！如果先 cnt[sum]++ 再查 sum-k，会把当前 sum 自身也算进去
3. 滚动变量 sum 替代 prefix 数组——前缀和只依赖前一个值，无需保存历史，省 O(n) 空间

七、总结与适用场景

前缀和核心要点

维度	要点
本质	预处理前缀和数组，用做差把区间/子矩阵求和降到 O(1)
时间复杂度	预处理 O(n) / O(nm)，单次查询 O(1)
空间复杂度	O(n) / O(nm)——空间换时间
识别信号	"多次询问区间和""子矩阵和""和为 k 的子数组""差分数组"
常见变体	一维、二维、差分（前缀和的逆运算）、前缀和 + 哈希、前缀异或

典型题目清单

LeetCode 303：区域和检索（一维，基础）
LeetCode 304：二维区域和检索（二维）
LeetCode 560：和为 K 的子数组（一维 + 哈希）
LeetCode 523：连续子数组和（一维 + 哈希 + 同余）
LeetCode 1109：航班预订统计（差分）
LeetCode 1314：矩阵区域和（二维 + 边界处理）
LeetCode 238：除自身以外数组的乘积（前缀积 + 后缀积）
LeetCode 437：路径总和 III（树上前缀和）
LeetCode 1442：形成异或和的三元组数目（前缀异或 + 哈希）

🎯 记忆口诀
"前缀和做差即区间，哨兵下标避越界；二维容斥加左上，哈希配对找和 k。"
这四句覆盖了前缀和的四大场景：一维区间、二维子矩阵、哨兵技巧、与哈希组合的"和为 k"问题。遇到"区间求和"类题目，第一反应就该是前缀和。