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

前缀和：

前缀和（Prefix Sum）是一种常用的算法技巧，用于快速计算数组中某一范围的元素之和。 具体来说，前缀和是通过一个新的数组 prefix_sum 来表示原数组每个位置之前（包括当前位置）的所有元素之和。

• 这样可以将查询区间和的时间复杂度从 O(n) 降低到 O(1)。 下面两个关于前缀和的模板题

[【模板】前缀和]( programming/question- ranking&sourceUrl=/exam/oj?page=1&tab=%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587&topicId=196) #include 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 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& nums) { // 获取数组的大小 int n = nums.size(); // 创建两个辅助数组，dp1 和 dp2，用来存储前缀和与后缀和 vector dp1(n); // dp1[i] 存储 nums[0] 到 nums[i-1] 的和 vector 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)，从而提升了程序的效率。

[除自身以外的数组的乘积](

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

class Solution { public: int subarraySum(vector& nums, int k) { // 使用哈希表记录前缀和出现的次数 unordered_map 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; } };

class Solution { public: int subarraysDivByK(vector& nums, int k) { // 使用哈希表记录每个前缀和的余数出现的次数 unordered_map 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& nums) { // 获取数组的大小 int n = nums.size(); // 哈希表用来存储前缀和出现的位置 unordered_map 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> matrixBlockSum(vector>& mat, int k) { // 获取矩阵的行数和列数 int m = mat.size(), n = mat[0].size(); // 创建一个 dp 数组，用来存储前缀和 // dp[i][j] 表示从 (0, 0) 到 (i-1, j-1) 的矩阵区域的和 vector> dp(m + 1, vector (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> ret(m, vector (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; } };