前缀和：

前缀和（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] 的索引 ifor(int i = 0; i < n; i++){if(dp1[i] == dp2[i])return i; // 如果找到匹配的索引，返回该索引}// 如果没有找到，返回 -1return -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 初始化为 1vector<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];// 初始化返回结果数组 retvector<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 的出现次数加 1hash[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 的出现次数加 1hash[r]++;}// 返回符合条件的子数组个数return ret;}
};

连续数组

class Solution 
{
public:int findMaxLength(vector<int>& nums) {// 获取数组的大小int n = nums.size();// 哈希表用来存储前缀和出现的位置unordered_map<int,int> hash;// 初始化哈希表，前缀和为 0 的时候，位置为 -1hash[0] = -1;// sum 用来记录当前的前缀和，ret 用来记录最长的子数组长度int sum = 0, ret = 0;// 遍历数组 nums，计算每个位置的前缀和for(int i = 0; i < n; i++){// 如果当前元素是 0，减 1；如果是 1，加 1sum += 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));// 计算前缀和数组 dpfor(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;   }
};