1.什么是前缀和

前缀和算法（Prefix Sum Algorithm）是一种常用的算法技巧，用于快速计算数组的某些子数组的和。它通过提前计算出数组中元素的累加和，来加速后续的区间和查询，特别适用于需要频繁查询子数组和的场景。

前缀和的基本思想

给定一个数组 A，前缀和数组 S是通过将 A中的每个元素累加得到的数组，具体来说，S[i]存储的是 A[0]到 A[i]的和。

• 前缀和数组的定义：

  S[i] = A[0] + A[1] + ... + A[i]

• 用前缀和数组来求区间和：通过前缀和数组，我们可以非常快速地求出任意区间 [L, R]的和，公式为：

  sum(L, R) = S[R] - S[L-1]

  其中 S[R]是从 A[0]到 A[R]的累加和，S[L-1]是从 A[0]到 A[L-1]的累加和，所以 S[R] - S[L-1]就是 A[L]到 A[R]的区间和。

具体步骤

1. 构建前缀和数组：

   • 初始化前缀和数组 S，其中 S[0] = A[0]。
   • 对于 i > 0，有：S[i] = S[i-1] + A[i]。

2. 查询区间和：

   • 对于任意区间 [L, R]，通过公式 sum(L, R) = S[R] - S[L-1]计算区间和。

优点

• 查询效率高：使用前缀和数组，区间和查询的时间复杂度为 O(1)，即常数时间。这使得处理大量区间和查询时非常高效。
• 预处理时间：构建前缀和数组的时间复杂度为 O(n)，其中 n是数组的长度。

缺点

• 空间复杂度：需要额外的空间来存储前缀和数组，空间复杂度为 O(n)。
• 适用场景：前缀和算法主要适用于静态数组或不经常更新的数组。如果数组频繁更新，前缀和算法的效率将受到影响，因为每次更新可能需要重新计算前缀和数组。

基本应用场景

1. 区间和查询：当你需要频繁查询一个数组的区间和时，前缀和算法是一个非常高效的解决方案。
2. 区间最小值/最大值查询：虽然前缀和主要用于求和，但其思想也可以扩展到其他的区间查询问题，如查询区间的最大值或最小值。
3. 二维数组问题：前缀和不仅适用于一维数组，也可以扩展到二维数组（矩阵），用于快速计算矩阵中任意子矩阵的和。

2.前缀和练习

 2.1 一维前缀和(模版)

示例：

输入：

3 21 2 41 22 3

输出：

36

这个题就是典型的求区间和

代码展示+算法思路

注意：题目l是大于等于1的，所以我们输入的数组是从1开始输入。

#include using namespace std;#include int main() {     int n,q;    cin>>n>>q;    vector arr(n+1);    for(int i=1;i<=n;i++)    cin>>arr[i];    vector sum(n+1);    for(int i=1;i<=n;i++)    sum[i]=sum[i-1]+arr[i];       for(int j=0;j>l>>r;    cout<

sum数组是前缀和数组，sum[i]存储的是从 arr[1]到 arr[i]的元素之和。

• 初始时，sum中的元素被设置为0
• 然后通过循环逐个计算前缀和：sum[i] = sum[i - 1] + arr[i]，也就是每个位置的前缀和是前一个位置的前缀和加上当前元素。

2.2 二维前缀和典型模版

算法思路分析

 填写前缀和矩阵数组的时候，下标直接从 1 开始，能大胆使用 i - 1 , j - 1 位置的值。 注意 dp 表与原数组 matrix 内的元素的映射关系： i. 从 dp 表到 matrix 矩阵，横纵坐标减一； ii. 从 matrix 矩阵到 dp 表，横纵坐标加一。

 使用前缀和矩阵

[x1,y1]----[x2,y2]的和

代码展示

#include #include using namespace std;int main() {     int n,m,q;    int arr[1010][1010];    long long dp[1010][1010];    cin>>n>>m>>q;    for(int i=1;i<=n;i++){     for(int j=1;j<=m;j++)    cin>>arr[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]+arr[i][j]-dp[i-1][j-1];    }    int x1,y1,x2,y2;    while(q--){         cin>>x1>>y1>>x2>>y2;        cout<

 还是采用的c语言形式定义二维数组比较简便，因为题目给出了行列的数据范围，所以我们直接定义1010为数组行列的个数，初始化都为0 ，不影响加的结果，当然后续遍历也不会用到多余的0数据。

2.3 寻找数组的中心下标 

724. 寻找数组的中心下标 - 力扣（LeetCode）

  通过读取题意就是求i前后区间的和判断是否相等，返回i即可。

class Solution { public:    int pivotIndex(vector& nums) {     int n=nums.size();    vector v1(n),v2(n);    for(int i=1;i=0;i--)      v2[i]=v2[i+1]+nums[i+1];      for(int i=0;i

2.4 除自身以外数组的乘积 

238. 除自身以外数组的乘积 - 力扣（LeetCode）

class Solution { public:    vector productExceptSelf(vector& nums) {         vectorv;        int n=nums.size();        vectorv1(n,1);        vectorv2(n,1);        for(int i=1;i=0;i--)        v2[i]=v2[i+1]*nums[i+1];               for(int i=0;i

 本题其实和上一道题思路很相似，将前后前缀和换成了前后前缀积

2.5 和为K的子数组

560. 和为 K 的子数组 - 力扣（LeetCode）

暴力枚举i区间内所有的子数组

class Solution { public:    int subarraySum(vector& nums, int k) {         int count = 0;        for (int start = 0; start < nums.size(); ++start) {             int sum = 0;            for (int end = start; end >= 0; --end) {                 sum += nums[end];                if (sum == k) {                     count++;                }            }        }        return count;    }};

但是会重复计算很多次相同数字的和 ，简单优化求出所有前缀和存放在数组中，在暴力枚举所有区间，统计等于k的个数。

class Solution { public:    int subarraySum(vector& nums, int k) {         int n=nums.size();        vectorv(n+1);        for(int i=1;i<=n;i++){          v[i]=v[i-1]+nums[i-1];        }        int count=0;        for(int i=1;i<=n;i++){             for(int j=0;j

 哈希+前缀和，将前缀和存在哈希表中。

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

结束语

本节内容就到此结束了，前缀和的题目还有很多，后续有时间也会继续更新前缀和的相关题目分享，也欢迎友友一起讨论。

最后，感谢各位友友的支持！！！