【前缀和的力量：高效解决子数组和矩阵问题的秘笈】—— 蓝桥杯高频热点题型知识点

前缀和：

前缀和（Prefix Sum）是一种常用的算法技巧，用于快速计算数组中某一范围的元素之和。

具体来说，前缀和是通过一个新的数组 prefix_sum 来表示原数组每个位置之前（包括当前位置）的所有元素之和。

• 这样可以将查询区间和的时间复杂度从 O(n) 降低到 O(1)。

下面两个关于前缀和的模板题

【模板】前缀和

#include <iostream>
using namespace std;

// 定义常量 N 来表示数组的大小
const int N = 1000001;

// 声明两个数组：'arr' 用来存储输入的值，'dp' 用来存储前缀和
long long arr[N], dp[N];

int main() 
{
    int n = 0, q = 0;
    
    // 读取数组的元素个数（n）和查询的数量（q）
    cin >> n >> q;
    
    // 读取数组元素到 'arr' 中
    for(int i = 1; i <= n; i++) cin >> arr[i];
    
    // 计算前缀和并存储在 'dp' 中
    // dp[i] 存储从 arr[1] 到 arr[i] 的和
    for(int i = 1; i <= n; i++) dp[i] = dp[i - 1] + arr[i];

    // 处理每个查询
    while(q--)
    {
        int l = 0, r = 0;
        
        // 读取当前查询的区间 [l, r]
        cin >> l >> r;
        
        // 输出从 arr[l] 到 arr[r] 的和，使用前缀和数组
        // dp[r] 给出的是从 arr[1] 到 arr[r] 的和，dp[l-1] 给出的是从 arr[1] 到 arr[l-1] 的和，
        // 因此 dp[r] - dp[l-1] 就是从 arr[l] 到 arr[r] 的和
        cout << dp[r] - dp[l - 1] << endl;
    }
    
    return 0;    
}

【模板】二维前缀和

#include <iostream>
using namespace std;

// 定义常量 N 来表示二维数组的大小
const int N = 1010;

// 声明二维数组 'arr' 用来存储输入的矩阵元素，'dp' 用来存储前缀和
long long arr[N][N], dp[N][N];

int main() 
{
    int n = 0, m = 0, q = 0;
    
    // 读取矩阵的行数（n）、列数（m）和查询的数量（q）
    cin >> n >> m >> q;
    
    // 读取矩阵元素到 'arr' 中
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            cin >> arr[i][j];
        }
    }

    // 计算前缀和并存储在 'dp' 中
    // dp[i][j] 存储从 (1,1) 到 (i,j) 的矩阵和
    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] - dp[i - 1][j - 1] + arr[i][j];
        }
    }

    // 处理每个查询
    while(q--)
    {
        int x1, y1, x2, y2;
        
        // 读取当前查询的矩阵区域 (x1, y1) 到 (x2, y2)
        cin >> x1 >> y1 >> x2 >> y2;
        
        // 计算并输出 (x1, y1) 到 (x2, y2) 区域的矩阵和
        // 利用前缀和数组 'dp' 计算矩阵区域的和
        // dp[x2][y2] 给出从 (1, 1) 到 (x2, y2) 的和，
        // dp[x1 - 1][y2] 给出从 (1, 1) 到 (x1-1, y2) 的和，
        // dp[x2][y1 - 1] 给出从 (1, 1) 到 (x2, y1-1) 的和，
        // dp[x1 - 1][y1 - 1] 给出从 (1, 1) 到 (x1-1, y1-1) 的和，
        // 通过这些前缀和，我们能够快速计算出 (x1, y1) 到 (x2, y2) 区域的和。
        cout << dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1] << endl;
    }
    
    return 0;    
}

通过上面两道模板题，我们可以总结出关于一维、以及二维关于前缀和的核心代码

• 一维：dp[i] = dp[i - 1] + arr[i]

• 二维：dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + arr[i][j]
  

寻找数组的中心下标

思路：
该题目与前缀和算法有很大的关系，因为其核心思想是通过前缀和来快速计算一个区间的和。

前缀和算法通常用于解决以下类型的问题：

• 计算数组某一子区间的和。
• 处理多个关于数组区间的查询问题。

class Solution 
{
public:
    int pivotIndex(vector<int>& nums) 
    {
        // 获取数组的大小
        int n = nums.size();
        
        // 创建两个辅助数组，dp1 和 dp2，用来存储前缀和与后缀和
        vector<int> dp1(n); // dp1[i] 存储 nums[0] 到 nums[i-1] 的和
        vector<int> dp2(n); // dp2[i] 存储 nums[i+1] 到 nums[n-1] 的和

        // 计算 dp1 数组，dp1[i] 表示 nums[0] 到 nums[i-1] 的和
        for(int i = 1; i < n; i++) 
            dp1[i] = dp1[i - 1] + nums[i - 1];

        // 计算 dp2 数组，dp2[i] 表示 nums[i+1] 到 nums[n-1] 的和
        for(int i = n - 2; i >= 0; i--) 
            dp2[i] = dp2[i + 1] + nums[i + 1];

        // 遍历数组，查找满足 dp1[i] == dp2[i] 的索引 i
        for(int i = 0; i < n; i++)
        {
            if(dp1[i] == dp2[i])
                return i; // 如果找到匹配的索引，返回该索引
        }

        // 如果没有找到，返回 -1
        return -1;
    }
};

该问题的关键在于通过 前缀和 和 后缀和 两个数组，分别计算数组每个元素左边和右边的和，然后判断哪个位置的左右和相等，来找出枢轴索引。利用前缀和的思想将原本需要 O(n^2) 的区间求和操作优化到 O(n)，从而提升了程序的效率。

除自身以外的数组的乘积

class Solution 
{
public:
    vector<int> productExceptSelf(vector<int>& nums) 
    {
        // 获取数组的大小
        int n = nums.size();
        
        // 初始化两个辅助数组 dp1 和 dp2，分别用来存储左边的乘积和右边的乘积
        // dp1[i] 存储 nums[0] 到 nums[i-1] 的所有元素的乘积
        // dp2[i] 存储 nums[i+1] 到 nums[n-1] 的所有元素的乘积
        vector<int> dp1(n, 1); // dp1 初始化为 1
        vector<int> dp2(n, 1); // dp2 初始化为 1

        // 计算 dp1 数组，dp1[i] 存储 nums[0] 到 nums[i-1] 的乘积
        for(int i = 1; i < n; i++) 
            dp1[i] = dp1[i - 1] * nums[i - 1];

        // 计算 dp2 数组，dp2[i] 存储 nums[i+1] 到 nums[n-1] 的乘积
        for(int i = n - 2; i >= 0; i--) 
            dp2[i] = dp2[i + 1] * nums[i + 1];

        // 初始化返回结果数组 ret
        vector<int> ret(n);

        // 计算最终结果，ret[i] 是 nums[0] 到 nums[i-1] 的乘积与 nums[i+1] 到 nums[n-1] 的乘积的乘积
        for(int i = 0; i < n; i++)
            ret[i] = dp2[i] * dp1[i]; 

        return ret; // 返回结果数组
    }
};

和为K的子数组

class Solution 
{
public:
    int subarraySum(vector<int>& nums, int k) 
    {
        // 使用哈希表记录前缀和出现的次数
        unordered_map<int, int> hash;
        
        // 初始化哈希表，前缀和为 0 出现 1 次（表示空数组的和为 0）
        hash[0] = 1;
        
        // 初始化变量 sum 来记录当前的前缀和，ret 来记录符合条件的子数组个数
        int sum = 0, ret = 0;
        
        // 遍历数组 nums，计算前缀和
        for(auto x : nums)
        {
            // 更新当前的前缀和
            sum += x;
            
            // 如果哈希表中存在 (sum - k)，说明当前前缀和与某个之前的前缀和之间的和为 k
            // 也就是说，找到了一个符合条件的子数组
            if(hash.count(sum - k)) 
                ret += hash[sum - k];
            
            // 更新哈希表，将当前前缀和 sum 的出现次数加 1
            hash[sum]++;
        }
        
        // 返回符合条件的子数组个数
        return ret;
    }
};

和可被K整除的数组

class Solution 
{
public:
    int subarraysDivByK(vector<int>& nums, int k) 
    {
        // 使用哈希表记录每个前缀和的余数出现的次数
        unordered_map<int, int> hash;
        
        // 初始化哈希表，前缀和的余数为 0 出现 1 次（表示空数组的和为 0）
        hash[0] = 1;

        // 初始化变量 sum 来记录当前的前缀和，ret 来记录符合条件的子数组个数
        int sum = 0, ret = 0;

        // 遍历数组 nums，计算前缀和
        for(auto x : nums)
        {
            // 更新当前的前缀和
            sum += x;

            // 计算当前前缀和的余数
            // (sum % k + k) % k 确保余数为非负数
            int r = (sum % k + k) % k;
            
            // 如果哈希表中存在余数 r，说明存在符合条件的子数组
            if(hash.count(r)) 
                ret += hash[r];

            // 更新哈希表，将当前余数 r 的出现次数加 1
            hash[r]++;
        }
        
        // 返回符合条件的子数组个数
        return ret;
    }
};

连续数组

class Solution 
{
public:
    int findMaxLength(vector<int>& nums) 
    {
        // 获取数组的大小
        int n = nums.size();
        
        // 哈希表用来存储前缀和出现的位置
        unordered_map<int,int> hash;
        
        // 初始化哈希表，前缀和为 0 的时候，位置为 -1
        hash[0] = -1;

        // sum 用来记录当前的前缀和，ret 用来记录最长的子数组长度
        int sum = 0, ret = 0;

        // 遍历数组 nums，计算每个位置的前缀和
        for(int i = 0; i < n; i++)
        {
            // 如果当前元素是 0，减 1；如果是 1，加 1
            sum += nums[i] == 0 ? -1 : 1;

            // 如果当前前缀和之前已经出现过，说明存在符合条件的子数组
            // 通过 i - hash[sum] 计算当前符合条件的子数组的长度
            if(hash.count(sum)) 
                ret = max(ret, i - hash[sum]);
            else 
                // 如果前缀和没有出现过，则将当前前缀和和它的位置加入哈希表
                hash[sum] = i;
        }

        // 返回最长的子数组长度
        return ret;
    }
};

矩阵区域和

class Solution 
{
public:
    vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) 
    {
        // 获取矩阵的行数和列数
        int m = mat.size(), n = mat[0].size();
        
        // 创建一个 dp 数组，用来存储前缀和
        // dp[i][j] 表示从 (0, 0) 到 (i-1, j-1) 的矩阵区域的和
        vector<vector<int>> dp(m + 1, vector<int> (n + 1));
        
        // 计算前缀和数组 dp
        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];
            }
        }        
        
        // 初始化返回结果数组 ret，存储每个位置的子矩阵和
        vector<vector<int>> ret(m, vector<int> (n));
        
        // 遍历矩阵，计算每个位置的以 (i, j) 为中心，边长为 2k+1 的子矩阵和
        for(int i = 0; i < m; i++)
        {
            for(int j = 0; j < n; j++)
            {
                // 计算子矩阵的四个角的坐标
                int x1 = max(0, i - k) + 1, y1 = max(0, j - k) + 1;
                int x2 = min(m - 1, i + k) + 1, y2 = min(n - 1, j + k) + 1;
                
                // 利用前缀和计算当前 (i, j) 位置的子矩阵和
                ret[i][j] = dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1];
            }
        }     
        
        // 返回结果矩阵
        return ret;   
    }
};