算法深度剖析：前缀和

前言

本章将深度剖析前缀和，以及总结前缀和模板。

前缀和是一种在算法和数据处理中的重要技巧，特别适合解决连续子数组求和的问题。通过构建一个前缀和数组，我们可以快速查询任意连续区间的和，从而在一定程度上优化时间复杂度。

基本原理
前缀和的核心思想是预先计算数组的前缀和，使得区间求和可以在常数时间内完成。假设有一个数组 ( arr )，其前缀和数组定义如下：

• 设 ( prefix[i] ) 表示从数组起点到位置 ( i ) 的元素之和。
• 因此，前缀和数组 ( prefix ) 可以定义为：
  [
  prefix[i] = arr[0] + arr[1] + \dots + arr[i]
  ]

计算任意区间和 ( arr[l] + arr[l+1] + \dots + arr[r] ) 可以通过前缀和快速得到：
[
arr[l] + arr[l+1] + \dots + arr[r] = prefix[r] - prefix[l-1]
]
其中， ( prefix[r] ) 是从 ( arr[0] ) 到 ( arr[r] ) 的和，减去从 ( arr[0] ) 到 ( arr[l-1] ) 的和就得到了区间 ( [l, r] ) 的和。

例子
假设有数组 ( arr = [1, 2, 3, 4, 5] )，构建前缀和数组 ( prefix ) 如下：

• ( prefix[0] = 1 )
• ( prefix[1] = 1 + 2 = 3 )
• ( prefix[2] = 1 + 2 + 3 = 6 )
• ( prefix[3] = 1 + 2 + 3 + 4 = 10 )
• ( prefix[4] = 1 + 2 + 3 + 4 + 5 = 15 )

那么，求区间和 ( arr[1] + arr[2] + arr[3] ) 就可以通过前缀和数组计算：
[
arr[1] + arr[2] + arr[3] = prefix[3] - prefix[0] = 10 - 1 = 9
]

时间复杂度

• 构建前缀和数组的时间复杂度为 ( O(n) )，其中 ( n ) 是数组的长度。
• 一旦构建好前缀和数组，查询任意区间的和的时间复杂度为 ( O(1) )。

前缀和技术通常用于快速解决子数组求和、二维区域求和等问题。

一、一维前缀和模板

【模板】前缀和

#include <iostream>
using namespace std;
#include<vector>
typedef long long LL;

int n,q;

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

    //定义前缀和数组
    vector<LL> dp(n + 1);
    for (int i = 1; i <= n; i++)
    {
        dp[i] = dp[i - 1] + arr[i];
    }

    //使用前缀和数组
    while (q--)
    {
        LL l, r;
        cin >> l >> r;
        cout << dp[r] - dp[l - 1] << endl;
    }

    return 0;
}

二、二维前缀和模板

【模板】二维前缀和

#include <iostream>
using namespace std;

#include<vector>
typedef long long LL;

int main()
{
    int n, m, q;
    cin >> n >> m >> q;

    //初始化原始数据
    vector<vector<LL>> arr(n + 1, vector<LL> (m + 1));

    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            cin >> arr[i][j];
        }
    }

    //定义前缀和数组
    vector<vector<LL>> dp(n + 1, vector<LL> (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];
        }
    }

    //使用前缀和数组
    while (q--)
    {
        LL x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        cout << dp[x2][y2] - dp[x2][y1 - 1] - dp[x1 - 1][y2] + dp[x1 - 1][y1 - 1] << endl;
    }

    return 0;
}

三、寻找数组的中心下标

寻找数组的中心下标

算法思路：

根据中心下标的定义，除中心下标元素外，该元素左边的「前缀和」应等于右边的「后缀和」。

• 因此，可以先预处理两个数组，一个表示前缀和，另一个表示后缀和。
• 然后，用一个 for 循环枚举可能的中心下标，判断每个位置的前缀和和后缀和是否相等，如果相等，则返回该下标。

class Solution {
public:
    int pivotIndex(vector<int>& nums) 
    {
        int n = nums.size();
        //构建前缀和
        vector<int> dp_first(n);
        dp_first[0] = 0;
        for (int i = 1; i < n; i++)
        {
            dp_first[i] = dp_first[i - 1] + nums[i - 1];
        }
        
        //构建后缀和
        vector<int> dp_end(n);
        dp_end[n - 1] = 0;
        for (int i = n - 2; i >= 0; i--)
        {
            dp_end[i] = dp_end[i + 1] + nums[i + 1];
        }

        //使用前缀和
        for (int i = 0; i < n; i++)
        {
            if (dp_first[i] == dp_end[i])
                return i;
        }
        return -1;
    }
};

四、除自身以外数组的乘积

除自身以外数组的乘积

算法思路：

题目要求不能使用除法，并要求在 $O(N)$ 时间复杂度内完成，排除了暴力解法和计算数组乘积后除以单个元素的方法。

分析可知，每个位置的最终结果 ret[i] 可以分为两部分：

1. 前缀积部分：nums[0] * nums[1] * ... * nums[i - 1]
2. 后缀积部分：nums[i + 1] * nums[i + 2] * ... * nums[n - 1]

可以利用前缀和的思想，定义两个数组 post 和 suf，分别存储两部分信息：

1. post：表示 i 位置之前所有元素的前缀乘积，即 [0, i - 1] 区间的乘积。
2. suf：表示 i 位置之后所有元素的后缀乘积，即 [i + 1, n - 1] 区间的乘积。

最后，根据 post 和 suf 计算出每个位置的最终结果。

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) 
    {
        int n = nums.size();
        //构建前缀积
        vector<int> dp_first(n);
        dp_first[0] = 1;
        for (int i = 1; i < n; i++)
        {
            dp_first[i] = dp_first[i - 1] * nums[i - 1];
        }
        
        //构建后缀积
        vector<int> dp_end(n);
        dp_end[n - 1] = 1;
        for (int i = n - 2; i >= 0; i--)
        {
            dp_end[i] = dp_end[i + 1] * nums[i + 1];
        }

        //使用前后缀积
        vector<int> answer(n);
        for (int i = 0; i < n; i++)
        {
            answer[i] = dp_first[i] * dp_end[i];
        }
        return answer;
    }
};

五、和为 K 的子数组

和为 K 的子数组

（将前缀和存入哈希表）：

算法思路：

设 i 为数组中的任意位置，sum[i] 表示 [0, i] 区间内所有元素的和。

• 我们需要找到“以 i 为结尾且和为 k 的子数组”，这等价于找出所有可能的起始位置 x1, x2, x3...，使得 [x, i] 区间的和为 k。
• 此时，[0, x] 区间的和应为 sum[i] - k。

因此，问题转化为：

• 找出 [0, i - 1] 区间内有多少前缀和等于 sum[i] - k。

无需真正初始化前缀和数组，因为我们只关注 i 位置之前，前缀和为 sum[i] - k 的次数。我们可以使用一个哈希表，在计算当前位置的前缀和时，同时记录每个前缀和出现的次数。

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) 
    {
        // 哈希表模拟前缀和数组
        unordered_map<int, int> hash;
        hash[0] = 1;

        //使用前缀和数组
        int sum = 0, ret = 0;

        for (auto e : nums)
        {
            sum += e;
            if (hash.count(sum - k)) ret += hash[sum - k];
            hash[sum]++;
        }
        return ret;
    }
}; 

六、和可被 K 整除的子数组

和可被 K 整除的子数组



本题需要的前置知识：

• 同余定理：
  若 (a - b) % n == 0，则 a % n == b % n。也就是说，如果两个数之差能被 n 整除，那么这两个数对 n 取模的结果相同。
  例如，(26 - 2) % 12 == 0，所以 26 % 12 == 2 % 12 == 2。

• C++ 中负数取模结果的处理：

  • 在 C++ 中，负数取模的结果会保留负号，例如 -1 % 3 = -1。
  • 为防止负数结果影响，常用 (a % n + n) % n 确保结果为正，例如：-1 % 3 = (-1 % 3 + 3) % 3 = 2。

算法思路：

此题与 LeetCode 560 题“和为 K 的子数组”思路类似。

设 i 为数组中的任意位置，sum[i] 表示 [0, i] 区间内的和。

• 要找出“以 i 为结尾、和可被 k 整除的子数组”，需要找到所有起点 x1, x2, x3... 使得 [x, i] 的和能被 k 整除。
• 假设 [0, x - 1] 的和为 a，[0, i] 的和为 b，则有 (b - a) % k == 0。
• 根据同余定理，[0, x - 1] 区间和 [0, i] 区间的前缀和同余。因此问题变成：
  • 找到 [0, i - 1] 中前缀和的余数等于 sum[i] % k 的个数。

无需初始化前缀和数组，只需用一个哈希表记录每种前缀和的出现次数，同时计算当前位置的前缀和。

class Solution {
public:
    int subarraysDivByK(vector<int>& nums, int k) 
    {
        // 哈希表模拟前缀和数组
        unordered_map<int,int> hash;
        hash[0] = 1;
        //使用前缀和数组
        int sum = 0, ret = 0;
        for (auto e : nums)
        {
            sum += e;
            int r = (sum % k + k) % k;
            if (hash.count(r)) ret += hash[r];
            hash[r]++;
        }
        return ret;
    }
};

七、连续数组

连续数组

算法思路：

稍作转换，这道题可以化为经典问题：

• 本题需要找一个连续区间，使得 0 和 1 出现的次数相同。
• 将 0 视为 -1，1 视为 1，问题就转化为找一个区间，使其和等于 0。

这样问题与 LeetCode 560 题“和为 K 的子数组”思路相似。

设 i 为数组中任意位置，用 sum[i] 表示 [0, i] 区间内所有元素的和。我们希望找到最大长度的“以 i 为结尾、和为 0 的子数组”，这需要找到从左至右第一个位置 x1 使得 [x1, i] 的和为 0。此时 [0, x1 - 1] 区间的和等于 sum[i]。因此问题变成：

• 找到 [0, i - 1] 区间内首次出现 sum[i] 的位置即可。

我们无需真正初始化一个前缀和数组，因为只关心 i 位置之前，首次出现等于 sum[i] 的前缀和位置。只需一个哈希表，在计算当前位置前缀和的同时，记录该前缀和的首次出现位置。

class Solution {
public:
    int findMaxLength(vector<int>& nums) 
    {
        // 哈希表模拟前缀和数组
        unordered_map<int, int> hash;
        hash[0] = -1; 

        // 使用前缀和数组
        int sum = 0, ret = 0;
        for (int i = 0; i < nums.size(); i++)
        {
            sum += nums[i] == 0 ? -1 : 1;
            if (hash.count(sum)) ret = max(ret, i - hash[sum]);
            else hash[sum] = i;
        }    
        return ret;
    }
};

八、矩阵区域和

矩阵区域和

算法思路：

这道题主要是二维前缀和的基本应用，关键在于填写结果矩阵时，找到原矩阵对应区域的「左上角」和「右下角」坐标（建议画图理解）。

• 左上角坐标：x1 = i - k，y1 = j - k，为了不超出矩阵范围，需要对 0 取 max，修正后的坐标为：x1 = max(0, i - k)，y1 = max(0, j - k)。
• 右下角坐标：x2 = i + k，y2 = j + k，同理，为避免超出矩阵范围，需要对 m - 1 和 n - 1 取 min，修正后的坐标为：x2 = min(m - 1, i + k)，y2 = min(n - 1, j + k)。

最后将修正后的坐标代入二维前缀和的计算公式即可（注意下标的映射关系）。

class Solution {
public:
    vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) 
    {
        // 构建二维前缀和
        int n = mat.size(), m = mat[0].size();
        vector<vector<int>> dp(n + 1, vector<int> (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] + mat[i - 1][j - 1] - dp[i - 1][j - 1];
            }
        }   

        //使用二维前缀和
        vector<vector<int>> answer(n, vector<int> (m));
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                int a, b, c, d;
                a = i - k < 0 ? 1 : i - k + 1;
                b = j - k < 0 ? 1 : j - k + 1;
                c = i + k >= n ? n : i + k + 1;
                d = j + k >= m ? m : j + k + 1;
                answer[i][j] = dp[c][d] - dp[c][b - 1] - dp[a - 1][d] + dp[a - 1][b - 1];
            }
        }
        return answer;
    }
};