1. 什么是前缀和算法

前缀和算法（Prefix Sum）是一种用于快速计算数组元素之和的技术。它通过预先计算数组中每个位置前所有元素的累加和，将这些部分和存储在一个新的数组中，从而在需要计算某个区间的和时，可以通过简单的减法操作得到结果，而不必重新遍历整个区间。

2. 一维前缀和

在这里我们通过一个例题来讲解：【模板】前缀和_牛客题霸_牛客网 (nowcoder.com)

题目描述如下

我们在一个数组中想要q次访问一段下标为 [l, r] 的数据和即

我们稍加分析可以发现，如果我们使用暴力解法（将区间内所有数字相加）时间复杂度为O(q*N)，在这里我们可以使用前缀和的算法，来使每次访问的时间复杂度降低到O(1)，在这里我们要提前预备好一个dp数组，dp[i]表示从下标1开始到下标i的数值和，dp[i] = dp[i-1] + arr[i]，这样填完dp表后，[l, r]的数值和sum = dp[r] - dp[l-1]，此外在这里有一个细节需要我们注意：下标为什么是从1开始的？——假如要计算[0, 2]的话，我们需要使用dp[2] - dp[-1]，这样就会带来不便。

我们可以得到这道题的代码

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

int main() 
{
    int n = 0, q = 0;
    cin >> n >> q;
    vector<int> arr(n + 1);
    for (int i = 1; i <= n; i++) cin >> arr[i];

    // 使用long long 避免整型溢出
    vector<long long> dp(n + 1);
    for (int i = 1; i <= n; i++) dp[i] = dp[i-1] + arr[i];

    int l = 0, r = 0;
    while (q--)
    {
        cin >> l >> r;
        cout << dp[r] - dp[l-1] << endl;
    }

    return 0;
}

3. 二维前缀和

在这里我们使用另一个例题：【模板】二维前缀和_牛客题霸_牛客网 (nowcoder.com)

在这里，我们需要得到从下标(x1, y1)->(x2, y2)所有数值和，我们同样可以使用前缀和来解决。二维的前缀和与一维的相似，我们可以规定dp[i][j]表示从下标(1, 1)->(i, j)所有数值和，我们要计算的dp[i][j]可以按如下方式计算

即dp[i][j] = dp[i-1][j] + dp[i][j-1] + arr[i][j] - dp[i-1][j-1]，在预备好了dp数组过后，我们如何来使用它呢？图解如下

我们可以使用如下代码解决此问题

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

int main() 
{
    int n = 0, m = 0, q = 0;
    cin >> n >> m >> q;
    vector<vector<int>> arr(n + 1, vector<int>(m + 1));
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> arr[i][j];

    vector<vector<long long>> dp(n + 1, vector<long long>(m + 1));
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            dp[i][j] = dp[i-1][j] + dp[i][j-1] + arr[i][j] - dp[i-1][j-1];

    int x1 = 0, y1 = 0, x2 = 0, y2 = 0;
    while (q--)
    {
        cin >> x1 >> y1 >> x2 >> y2;
        cout << dp[x2][y2] - dp[x1-1][y2] - dp[x2][y1-1] + dp[x1-1][y1-1] << endl;
    }

    return 0;
}

4. 应用实例

1. 寻找数组的中心下标

题目链接：724. 寻找数组的中心下标 - 力扣（LeetCode）

题目解析：分析题目后我们可以发现我们要得到一个下标的左边全部数据和与右边全部数据和，那么我们就可以使用前缀和算法来解决这道问题，即

结合模板可以得到代码

class Solution
{
public:
    int pivotIndex(vector<int>& nums)
    {
        int n = nums.size();
        vector<int> dp(n+1);
        for (int i = 1; i <= n; i++) dp[i] = dp[i-1] + nums[i-1];

        for (int i = 0; i < n; i++) if (dp[i] == (dp[n] - dp[i+1])) return i;

        return -1;
    }
};

除了这种解法外我们还可以分别创建一个前缀和数组与后缀和数组，来分别统计当前下标左边数据和与当前下标右边数据和，即

可以得到如下代码

class Solution
{
public:
    int pivotIndex(vector<int>& nums)
    {
        int n = nums.size();
        vector<int> f(n);
        vector<int> g(n);
        for (int i = 1; i < n; i++) f[i] = f[i - 1] + nums[i - 1];
        for (int i = n - 2; i >= 0; i--) g[i] = g[i + 1] + nums[i + 1];

        for (int i = 0; i < n; i++) if (f[i] == g[i]) return i;

        return -1;
    }
};