算法——前缀和算法

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;
    }
};

2. 除自身以外数组的乘积

题目链接：238. 除自身以外数组的乘积 - 力扣（LeetCode）

解析：由题可知，我们可以初始化一个前缀积数组front与后缀积数组back，并在res返回数组中取得对应的前后缀并相乘，即

结合模板有

class Solution 
{
public:
    vector<int> productExceptSelf(vector<int>& nums) 
    {
        int n = nums.size();
 
        vector<int> front(n + 1);
        vector<int> back(n + 1);
        front[0] = front[1] = back[n-1] = back[n] = 1;
        for (int i = 2; i <= n; i++) front[i] = front[i-1] * nums[i-2];
        for (int i = n-2; i >= 0; i--) back[i] = back[i+1] * nums[i+1];
 
        vector<int> res(n);
        for (int i = 0; i < n; i++) res[i] = front[i+1] * back[i];
        
        return res;
    }
};

3. 和为K的子数组

题目链接：560. 和为 K 的子数组 - 力扣（LeetCode）

解析：看到这个题目我们可以发现，使用暴力解法（定位一个起点从前往后遍历一遍），其时间复杂度为O(N^2)，在这里由于数组中的数据有正有负，因此我们无法使用双指针来对其进行优化，而可以采用前缀和的思想来优化，即

代码如下

class Solution 
{
public:
    int subarraySum(vector<int>& nums, int k) 
    {
        int ret = 0;
        int n = nums.size();
        // 哈希表统计次数
        unordered_map<int, int> hash;
        // 提前统计如果整个数组的和为k的情况
        hash[0] = 1;
 
        int sumi = 0;
        for (int i = 0; i < n; i++)
        {
            // 使用sumi来优化(避免额外创建一个前缀和数组)
            sumi += nums[i];
            // 直接判断hash表中sumi-k的个数(和为k的子数组的个数)
            // 只要sumi-k存在，说明该位置到i位置的和为k
            if (hash.count(sumi - k)) ret += hash[sumi - k];
            // 将当前位置的前缀和放入哈希表
            hash[sumi]++;
        }
 
        return ret;
    }
};

4. 和可被K整除的子数组

题目链接：974. 和可被 K 整除的子数组 - 力扣（LeetCode）

解析：这道题与第3题类似，根据第三题的思路，我们需要找到sumi-k与k之间的关系，这就需要我们用到同余定理

两个整数a、b，如果他们同时除以一个自然数k，所得的余数相同，则称a、b对于模m同余，举个例子：16%7=2, 9%7=2, 我们可以得到16-9=n*7，即a-b=n*m

在这里我们需要使用的是(a-b)÷m=k......0 => a%m=b%m，转换成我们这道题里的意思就是，要寻找能被k整除的区间即寻找(sum-x)%k=0 => sum%k==x%k这样一个区间，即

此外，我们还需要注意一个细节就是一个负数%正数的时候，其结果会是负数，我们可以使用(sum%k + k)来修正这个负数，但是当sum为正时，我们会多加一个k此时再%k即可解决，因此我们的修正公式为(sum%k + k)%k，细节问题与上面的第3题类似，这里就不过多赘述，代码如下

class Solution 
{
public:
    int subarraysDivByK(vector<int>& nums, int k) 
    {
        int ret = 0;
        unordered_map<int, int> hash;
        hash[0] = 1;
 
        int sum = 0;
        for (auto e : nums)
        {
            sum += e;
            int mod = (sum % k + k) % k;
            if (hash.count(mod)) ret += hash[mod];
            hash[mod]++;
        }
 
        return ret;
    }
};

5. 连续数组

题目链接：525. 连续数组 - 力扣（LeetCode）

解析：对于这道题我们直接解决还是有点困难，可以先将0转换成-1，这样就与我们之前做的和为k的子数组相似了，我们还是可以定义dp[i]是以i位置为结尾的所有子数组，要想找到和为0的子数组只需要找到sum相同的区间，并计算这个区间的长度，图示如下

我们要想知道区间长度，就需要知道i和j，因此我们向哈希表中存入的value为当前前缀和的下标。此外，如果我们再次遇到一个值为sum的下标，由于这里求得是最长区间，所以我们不需要更新hash[sum]。而如果整个区间的长度都为0，那么我们就需要在前缀和为0的情况下，找到一个下标为-1的地方来统计整个数组长度。此外，我们计算长度时，图解如下

我们可以得到代码如下

class Solution 
{
public:
    int findMaxLength(vector<int>& nums) 
    {
        for (auto& e : nums) if (e == 0) e = -1;
        unordered_map<int, int> hash;
        hash[0] = -1;
 
        int ret = 0;
        int sum = 0;
        for (int i = 0; i < nums.size(); i++)
        {
            sum += nums[i];
            if (hash.count(sum)) ret = max(ret, i - hash[sum]);
            else hash[sum] = i;
        }
 
        return ret;
    }
};

6. 矩阵区域和

题目链接：1314. 矩阵区域和 - 力扣（LeetCode）

解析： 在之前我们已经推导过二维前缀和的初始化与使用，在这里我们需要关注的是下标在dp数组与mat数组之间的映射关系，为了便于初始化我们将dp设置成一个大小为(n+1)*(m+1)的数组，因此dp[i][j]就对应着mat[i-1][j-1]。分析一下题意我们可以知道，这道题的意思是ret[i][j]表示从(i-k, j-k)->(i+k, j+k)的所有数值之和，且下标均要合法，我们可以使用min与max函数来分别控制下标有效，那么我们可以得到如下代码

class Solution 
{
public:
    vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) 
    {
        int m = mat.size(), n = mat[0].size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));
        for (int i = 1; i <= m; i++)
            for (int j = 1; j <= n; j++)
                dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + mat[i-1][j-1];
 
        vector<vector<int>> ret(m, vector<int>(n));
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
            {
                int x1 = max(i - k, 0), y1 = max(j - k, 0);
                int x2 = min(i + k, m - 1), y2 = min(j + k, n - 1);
                ret[i][j] = dp[x2+1][y2+1] - dp[x1][y2+1] - dp[x2+1][y1] + dp[x1][y1];
            }
 
        return ret;
    }
};