算法魅力之牛叉的前缀和

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 2
1 2 4
1 2
2 3

输出：

3
6

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

代码展示+算法思路

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

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

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 <iostream>
#include <vector>
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<<dp[x2][y2]-dp[x2][y1-1]-dp[x1-1][y2]+dp[x1-1][y1-1]<<endl;
    }
}

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

2.3 寻找数组的中心下标 

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

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

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

2.4 除自身以外数组的乘积 

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

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        vector<int >v;
        int n=nums.size();
        vector<int>v1(n,1);
        vector<int>v2(n,1);
        for(int i=1;i<n;i++)
        v1[i]=v1[i-1]*nums[i-1];
        for(int i=n-2;i>=0;i--)
        v2[i]=v2[i+1]*nums[i+1];
       
        for(int i=0;i<n;i++)
        v.push_back(v1[i]*v2[i]);
        return v;
    }
};

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

2.5 和为K的子数组

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

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

class Solution {
public:
    int subarraySum(vector<int>& 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<int>& nums, int k) {
        int n=nums.size();
        vector<int>v(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<i;j++)
            if(v[i]-v[j]==k)
            count++;
        }
        return count;
    }
};

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

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        unordered_map<int,int> 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;
    }
};

结束语

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

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

原文地址：https://blog.csdn.net/2302_79376097/article/details/144121352

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！