算法每日双题精讲 —— 前缀和（【模板】一维前缀和，【模板】二维前缀和）

在算法竞赛与日常编程中，前缀和是一种极为实用的预处理技巧，能显著提升处理区间和问题的效率。今天，我们就来深入剖析一维前缀和与二维前缀和这两个经典模板。

一、【模板】一维前缀和

题目描述

给定一个长度为 $n$ 的整数数组 $a$，我们需要完成以下两个任务：

1. 预处理数组，得到前缀和数组。
2. 能够快速查询数组中任意区间 $[l,r]$（$0\le l\le r<n$）内所有元素的和。

算法原理

一维前缀和的核心思想是预先计算数组中每个位置之前所有元素的总和。设前缀和数组为 $s$，其中 $s[i]$ 表示数组 $a$ 中前 $i$ 个元素的和（$i$ 从 $1$ 开始），那么有递推公式：
[s[i] = s[i - 1]+a[i - 1]]
这里 $s[0]=0$，是为了方便处理边界情况。

当我们需要查询区间 $[l,r]$ 的和时，根据前缀和的性质，该区间的和可以通过 $s[r+1]-s[l]$ 快速得到。这是因为 $s[r+1]$ 包含了前 $r+1$ 个元素的和，$s[l]$ 包含了前 $l$ 个元素的和，两者相减就得到了区间 $[l,r]$ 的和。

C++ 代码实现

#include <iostream>
#include <vector>

using namespace std;

// 计算一维前缀和数组
vector<int> calculatePrefixSum(const vector<int>& a) {
    int n = a.size();
    vector<int> s(n + 1, 0);
    for (int i = 1; i <= n; ++i) {
        s[i] = s[i - 1] + a[i - 1];
    }
    return s;
}

// 查询区间 [l, r] 的和
int querySum(const vector<int>& s, int l, int r) {
    return s[r + 1] - s[l];
}

int main() {
    vector<int> a = {1, 2, 3, 4, 5};
    vector<int> s = calculatePrefixSum(a);

    int l = 1, r = 3;
    cout << "The sum of the interval [" << l << ", " << r << "] is: " << querySum(s, l, r) << endl;

    return 0;
}

复杂度分析

• 时间复杂度：计算前缀和数组的时间复杂度为 $O(n)$，因为需要遍历数组一次。每次查询区间和的时间复杂度为 $O(1)$，这使得在多次查询的场景下，一维前缀和算法具有很高的效率。
• 空间复杂度：需要额外的长度为 $n+1$ 的数组来存储前缀和，因此空间复杂度为 $O(n)$。

二、【模板】二维前缀和

题目描述

给定一个 $m\times n$ 的二维整数矩阵 $A$，我们要完成以下任务：

1. 预处理矩阵，得到二维前缀和矩阵。
2. 能够快速查询矩阵中任意子矩阵 $[(x_1,y_1),(x_2,y_2)]$（$0\le x_1\le x_2<m$，$0\le y_1\le y_2<n$）内所有元素的和。

算法原理

对于二维前缀和，我们定义 $S[i][j]$ 表示矩阵 $A$ 中从左上角 $(0,0)$ 到右下角 $(i-1,j-1)$ 这个子矩阵内所有元素的和（$i$ 和 $j$ 从 $1$ 开始）。其递推公式如下：
$S[i][j]=S[i-1][j]+S[i][j-1]-S[i-1][j-1]+A[i-1][j-1]$
这里减去 $S[i-1][j-1]$ 是为了避免重复计算。

当查询子矩阵 $[(x_1,y_1),(x_2,y_2)]$ 的和时，公式为：
$sum=S[x_2+1][y_2+1]-S[x_1][y_2+1]-S[x_2+1][y_1]+S[x_1][y_1]$

C++ 代码实现

#include <iostream>
#include <vector>

using namespace std;

// 计算二维前缀和矩阵
vector<vector<int>> calculateTwoDPrefixSum(const vector<vector<int>>& A) {
    int m = A.size();
    int n = A[0].size();
    vector<vector<int>> S(m + 1, vector<int>(n + 1, 0));
    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            S[i][j] = S[i - 1][j] + S[i][j - 1] - S[i - 1][j - 1] + A[i - 1][j - 1];
        }
    }
    return S;
}

// 查询子矩阵 [(x1, y1), (x2, y2)] 的和
int queryTwoDSum(const vector<vector<int>>& S, int x1, int y1, int x2, int y2) {
    return S[x2 + 1][y2 + 1] - S[x1][y2 + 1] - S[x2 + 1][y1] + S[x1][y1];
}

int main() {
    vector<vector<int>> A = {
        {1, 2, 3},
        {4, 5, 6},
        {7, 8, 9}
    };
    vector<vector<int>> S = calculateTwoDPrefixSum(A);

    int x1 = 0, y1 = 0, x2 = 1, y2 = 1;
    cout << "The sum of the sub - matrix [(" << x1 << ", " << y1 << "), (" << x2 << ", " << y2 << ")] is: "
         << queryTwoDSum(S, x1, y1, x2, y2) << endl;

    return 0;
}

复杂度分析

• 时间复杂度：计算二维前缀和矩阵需要两层嵌套循环遍历矩阵，时间复杂度为 $O(m\times n)$。每次查询子矩阵和的时间复杂度为 $O(1)$，这使得在多次查询子矩阵和的场景下，二维前缀和算法非常高效。
• 空间复杂度：需要额外的 $(m+1)\times (n+1)$ 大小的矩阵来存储二维前缀和，因此空间复杂度为 $O(m\times n)$。

通过以上的讲解和代码实现，我们可以看到前缀和算法在处理区间和与子矩阵和问题时的强大威力。它通过预处理的方式，将原本可能需要 $O(n)$ 或 $O(m\times n)$ 时间复杂度的查询操作优化到了 $O(1)$，在实际应用中能显著提升程序的性能。希望大家能够熟练掌握这两个模板，并在后续的算法学习和实践中灵活运用。