C++优选算法四 前缀和

前缀和算法是一种常用的优化技术，主要用于加速某些涉及连续子数组或子序列求和的问题。

一、定义与原理

• 定义：前缀和是指数组中某个位置之前（包括该位置）所有元素的和。前缀和算法则是通过提前计算并存储这些前缀和，以便在后续查询中可以快速获取任意区间的和。
• 原理：该算法基于一个简单但强大的思想，即通过一次遍历数组，计算出每个位置的前缀和，并将其保存在一个额外的数组中。这样，在查询时，只需要简单地减去两个前缀和即可得到所需子数组的和。

二、示例题目

1.【模板】前缀和_牛客题霸_牛客网

解法(前缀和)
算法思路:
a.先预处理出来一个「前缀和」数组:
用 dp[i]表示:[1，i]区间内所有元素的和，那么 dp[i- 1]里面存的就是[1，i- 1]区间内所有元素的和，那么:可得递推公式:dp[i]= dp[i- 1]+arr[i];

b.「快速」求出「某一个区间内」所有元素的和:使用前缀和数组，当询问的区间是 [l，r]时:区间内所有元素的和为:dp[r]- dp[l - 1]。

#include <iostream>
#include<vector>
using namespace std;

int main() 
{
    int n=0,q=0;
    cin>>n>>q;
    vector<long long> vv(n+1);
    for(int i=1;i<=n;i++)
    {
        cin>>vv[i];
    }
    vector<long long> dp(n+1);//额外的数组存储前缀和

    for(int i=1;i<=n;i++)
    {
        dp[i]=dp[i-1]+vv[i];//根据递推公式计算前缀和
    }
    int l=0,r=0;
    for(int i=0;i<q;i++)
    {
        cin>>l>>r;
        cout<<dp[r]-dp[l-1]<<endl;
    }
    return 0;
}

 2.【模板】二维前缀和_牛客题霸_牛客网

解法:
算法思路:
类比于一维数组的形式，如果我们能处理出来从[0，0]位置到[i，j]位置这片区域内所有元素的累加和，就可以在 0(1)的时间内，搞定矩阵内任意区域内所有元素的累加和。因此我们接下来仅需完成两步即可:

• 第一步:搞出来前缀和矩阵

        这里就要用到一维数组里面的拓展知识，我们要在矩阵的最上面和最左边添加上一行和一列0，这样我们就可以省去非常多的边界条件的处理，处理后的矩阵就像这样: 

这样，我们填写前缀和矩阵数组的时候，下标直接从1开始，能大胆使用 i-1, j-1 位置的值。
注意 dp 表与原数组 matrix 内的元素的映射关系

• 从 dp 表到 matrix 矩阵，横纵坐标减一
• 从 matrix矩阵到 dp 表，横纵坐标加一

前缀和矩阵中 sum[i][j] 的含义,以及如何递推二维前缀和方程sum[i][j] 的含义:

a.sum[i][j]表示，从[0，0〕位置到[i，j]位置这段区域内，所有元素的累加和。

对应下图的红色区域:

b.递推方程:
其实这个递推方程非常像我们小学做过求图形面积的题，我们可以将[0，0]位置到[i，j]位置这段区域分解成下面的部分:

sum[i][j]=红+蓝+绿+黄，分析一下这四块区域:

• 黄色部分最简单，它就是数组中的 matrix[i- 1][j- 1](注意坐标的映射关系);
• 单独的蓝不好求，因为它不是我们定义的状态表示中的区域，同理，单独的绿也是;
• 但是如果是红+蓝，正好是我们 dp 数组中 sum[i - 1][j]的值;
• 同理，如果是红+绿，正好是我们 dp数组中 sum[i][j- 1]的值;
• 如果把上面求的三个值加起来，那就是黄+红+蓝+红+绿，发现多算了一部分红的面积因此再单独减去红的面积即可;
• 红的面积正好也是符合 dp 数组的定义的，即 sum[i- 1][j- 1]
• 综上所述，我们的递推方程就是:sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i - 1][j -1]+matrix[i-1][j- 1]

第二步:使用前缀和矩阵
题目的接口中提供的参数是原始矩阵的下标，为了避免下标映射错误，这里直接先把下标映射成dp表里面对应的下标:row1++, col1++, row2++,col2++

接下来分析如何使用这个前缀和矩阵，如下图(注意这里的row 和 col都处理过了，对应的正是 sum 矩阵中的下标)：

对于左上角(rowl，col1)、右下角(row2，col2)围成的区域，正好是红色的部分。因此我们要求的就是红色部分的面积，继续分析几个区域:

• 黄色，能直接求出来，就是 sum[row1-1，col1-1](为什么减一?因为要剔除掉 row 这一行和 col 这一列)
• 绿色，直接求不好求，但是和黄色拼起来，正好是 sum 表内 sum[row1 - 1][col2]的数据，
• 同理，蓝色不好求，但是蓝+黄= sum[row2][col1 - 1];
• iv.再看看整个面积，好求嘛?非常好求，正好是 sum[row2][col2];
• 那么，红色就=整个面积-黄-绿-蓝，但是绿蓝不好求，我们可以这样减:整个面积-(绿+黄)-(蓝+黄)，这样相当于多减去了一个黄，再加上即可。

综上所述:红=整个面积-(绿+黄)-(蓝+黄)+黄，从而可得红色区域内的元素总和为:sum[row2][col2]-sum[row2][col1-1]-sum[row1 - 1][col2]+sum[row1 -1][col-1]。

#include <iostream>
#include<vector>
using namespace std;

int main()
{
    int n=0,m=0,q=0;
    cin>>n>>m>>q;
    vector<vector<long long>> dp1(n+1,vector<long long>(m+1));
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>dp1[i][j];
        }
    }
    vector<vector<long long>> dp2(n+1,vector<long long>(m+1));
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            dp2[i][j]=dp2[i-1][j]+dp2[i][j-1]+dp1[i][j]-dp2[i-1][j-1];
        }
    }

    for(int i=0;i<q;i++)
    {
        int x1=0,x2=0,y1=0,y2=0;
        cin>>x1>>y1>>x2>>y2;
        cout<<dp2[x2][y2]-dp2[x1-1][y2]-dp2[x2][y1-1]+dp2[x1-1][y1-1]<<endl;
    }

    return 0;
}

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

给你一个整数数组 nums ，请计算数组的 中心下标 。

数组 中心下标 是数组的一个下标，其左侧所有元素相加的和等于右侧所有元素相加的和。

如果中心下标位于数组最左端，那么左侧数之和视为 0 ，因为在下标的左侧不存在元素。这一点对于中心下标位于数组最右端同样适用。

如果数组有多个中心下标，应该返回 最靠近左边 的那一个。如果数组不存在中心下标，返回 -1 。

示例 1：

输入：nums = [1, 7, 3, 6, 5, 6]
输出：3
解释：
中心下标是 3 。
左侧数之和 sum = nums[0] + nums[1] + nums[2] = 1 + 7 + 3 = 11 ，
右侧数之和 sum = nums[4] + nums[5] = 5 + 6 = 11 ，二者相等。

示例 2：

输入：nums = [1, 2, 3]
输出：-1
解释：
数组中不存在满足此条件的中心下标。

示例 3：

输入：nums = [2, 1, -1]
输出：0
解释：
中心下标是 0 。
左侧数之和 sum = 0 ，（下标 0 左侧不存在元素），
右侧数之和 sum = nums[1] + nums[2] = 1 + -1 = 0 。

解法(前缀和)
算法思路:
从中心下标的定义可知，除中心下标的元素外，该元素左边的「前缀和」等于该元素右边的「后缀和」。
因此，我们可以先预处理出来两个数组，一个表示前缀和，另一个表示后缀和。
然后，我们可以用一个 for 循环枚举可能的中心下标，判断每一个位置的「前缀和」以及「后缀和」，如果二者相等，就返回当前下标。 

class Solution {
public:
    int pivotIndex(vector<int>& nums) 
    {
        int n=nums.size();
        vector<int> f(n);//前缀和
        vector<int> g(n);//后缀和
        f[0]=g[n-1]=0;
        for(int i=1;i<n;i++)
        {
            f[i]=f[i-1]+nums[i-1];
        }
        for(int i=n-2;i>=0;i--)
        {
            g[i]=g[i+1]+nums[i+1];
        }
        for(int i=0;i<n;i++)
        {
            if(f[i]==g[i])
                return i;
        }
        return -1;
    }
};

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

给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。

题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在  32 位 整数范围内。

请 不要使用除法，且在 O(n) 时间复杂度内完成此题。

示例 1:

输入: nums = [1,2,3,4]

输出: [24,12,8,6]

示例 2:

输入: nums = [-1,1,0,-3,3]
输出: [0,0,9,0,0]

解法(前缀和数组)
算法思路:
注意题目的要求，不能使用除法，并且要在O(N)的时间复杂度内完成该题。那么我们就不能使用暴力的解法，以及求出整个数组的乘积，然后除以单个元素的方法。

继续分析，根据题意，对于每一个位置的最终结果ret[i]，它是由两部分组成的:

• nums[0] * nums[1] * nums[2] * ... * nums[i - 1]
• nums[i+1] * nums[i+2] * nums[n - 1]

于是，我们可以利用前缀和的思想，使用两个数组 post和 suf，分别处理出来两个信息:

• post 表示: i位置之前的所有元素，即[0，i- 1] 区间内所有元素的前缀乘积:
• suf 表示: i位置之后的所有元素，即[i+1，n-1]区间内所有元素的后缀乘积然后再处理最终结果。 

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) 
    {
        int n=nums.size();
        vector<int> f(n);//表示前缀乘积
        vector<int> g(n);//表示后缀乘积
        f[0]=g[n-1]=1;
        for(int i=1;i<n;i++)
        {
            f[i]=f[i-1]*nums[i-1];
        }
        for(int i=n-2;i>=0;i--)
        {
            g[i]=g[i+1]*nums[i+1];
        }
        vector<int> dp(n);
        for(int i=0;i<n;i++)
        {
            dp[i]=f[i]*g[i];
        }
        return dp;

    }
};

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

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。

子数组是数组中元素的连续非空序列。

示例 1：

输入：nums = [1,1,1], k = 2
输出：2

示例 2：

输入：nums = [1,2,3], k = 3
输出：2

解法（将前缀和存在哈希表中）

算法思路：

设 i 为数组中的任意位置，用 sum[i]表示[0，i] 区间内所有元素的和。想知道有多少个「以 i 为结尾的和为 k 的子数组」，就要找到有多少个起始位置为 x1，x2,x3... 使得[x，i]区间内的所有元素的和为 k。那么[0，x]区间内的和是不是就是sum[i]- k 了。于是问题就变成:
找到在[0，i- 1]区间内，有多少前缀和等于 sum[i]- k 的即可。我们不用真的初始化一个前缀和数组，因为我们只关心在 i 位置之前，有多少个前缀和等于sum[i]- k。因此，我们仅需用一个哈希表，一边求当前位置的前缀和，一边存下之前每一种前缀和出现的次数。

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 x:nums)
        {
            sum+=x;
            if(hash.count(sum-k))
                ret+=hash[sum-k];
            hash[sum]++;
        }
        return ret;
    }
};

 6.和可被K整除的子数组. - 力扣（LeetCode）

给定一个整数数组 nums 和一个整数 k ，返回其中元素之和可被 k 整除的非空 子数组 的数目。

子数组 是数组中 连续 的部分。

示例 1：

输入：nums = [4,5,0,-2,-3,1], k = 5
输出：7
解释：
有 7 个子数组满足其元素之和可被 k = 5 整除：
[4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]

示例 2:

输入: nums = [5], k = 9
输出: 0

解法(前缀和在哈希表中)
本题需要的前置知识:

• 同余定理

        如果(a- b)%n == 0，那么我们可以得到一个结论: a%n== b%n 。用文字叙述就是，如果两个数相减的差能被n整除，那么这两个数对n取模的结果相同。
例如:
(26-2)%12==0，那么 26%12 == 2 % 12 == 2.

• C++中负数取模的结果，以及如何修正「负数取模」的结果

        a.C++ 中关于负数的取模运算，结果是「把负数当成正数，取模之后的结果加上一个负号」。
例如:-1%3=-(1% 3)= -1
因为有负数，为了防止发生「出现负数」的结果，以(a%n+n)%n 的形式输出保证为正。
例如:-1%3=(-1%3+3)%3=2

算法思路：

设 i为数组中的任意位置，用表示 [0，i]区间内所有元素的和。

• 想知道有多少个「以 i 为结尾的可被 k 整除的子数组」，就要找到有多少个起始位置为 x1, x2, x3...使得[x，i ]区间内的所有元素的和可被 k 整除。
• 设[0，x]区间内所有元素之和等于 a，[0，i]区间内所有元素的和等于 b，可得:(b-a)%k==0;
• 由同余定理可得，[0,x-1]区间与[0，i] 区间内的前缀和同余。于是问题就变成: 找到在 [0,i-1]区间内，有多少前缀和的余数等于 sum[i] % k 的即可。

我们不用真的初始化一个前缀和数组，因为我们只关心在 i位置之前，有多少个前缀和等于sum[i]-k。因此，我们仅需用一个哈希表，一边求当前位置的前缀和，一边存下之前每一种前缀和出现的次数。 

class Solution {
public:
    int subarraysDivByK(vector<int>& nums, int k) 
    {
        unordered_map<int,int> hash;
        hash[0%k]=1;//0这个数的余数

        int sum=0,ret=0;
        for(auto x:nums)
        {
            sum+=x;//算出当前位置的前缀和
            int r=(sum%k+k)%k;//修正后的余数
            if(hash.count(r))
                ret+=hash[r];
            hash[r]++;
        }
        return ret;
    }
};

 7.连续数组. - 力扣（LeetCode）

给定一个二进制数组 nums , 找到含有相同数量的 0 和 1 的最长连续子数组，并返回该子数组的长度。

示例 1:

输入: nums = [0,1]
输出: 2
说明: [0, 1] 是具有相同数量 0 和 1 的最长连续子数组。

示例 2:

输入: nums = [0,1,0]
输出: 2
说明: [0, 1] (或 [1, 0]) 是具有相同数量0和1的最长连续子数组。

解法(前缀和在哈希表中)
算法思路:
稍微转化一下题目，就会变成我们熟悉的题:
本题让我们找出一段连续的区间，0和1出现的次数相同。
如果将 0记为-1，1记为 1，问题就变成了找出一段区间，这段区间的和等于 0于是，就和 【和为 K的子数组 】这道题的思路一样。

设 i为数组中的任意位置，用 sum[i]表示 [0，i]区间内所有元素的和。想知道最大的「以 i 为结尾的和为 0 的子数组」，就要找到从左往右第一个 x1 使得[x1，i]区间内的所有元素的和为 0。那么[0，x-1]区间内的和是不是就是 sum[i]了。于是问题就变成:

• ·找到在[0，i-1]区间内，第一次出现 sum[i]的位置即可。

我们不用真的初始化一个前缀和数组，因为我们只关心在 i 位置之前，第一个前缀和等于 sum[i]的位置。因此，我们仅需用一个哈希表，一边求当前位置的前缀和，一边记录第一次出现该前缀和的位置。

class Solution {
public:
    int findMaxLength(vector<int>& nums) 
    {
        unordered_map<int,int> hash;
        hash[0]=-1;//默认有一个前缀为0的情况
        int sum=0,ret=0;

        for(int i=0;i<nums.size();i++)
        {
            sum+=nums[i]==0?-1:1;//计算当前位置的前缀和
            if(hash.count(sum))
               ret=max(ret,i-hash[sum]);
            else
                hash[sum]=i; 
        }
        return ret;
    }
};

8.矩阵区域和. - 力扣（LeetCode）

给你一个 m x n 的矩阵 mat 和一个整数 k ，请你返回一个矩阵 answer ，其中每个 answer[i][j] 是所有满足下述条件的元素 mat[r][c] 的和： 

• i - k <= r <= i + k,
• j - k <= c <= j + k 且
• (r, c) 在矩阵内。

示例 1：

输入：mat = [[1,2,3],[4,5,6],[7,8,9]], k = 1
输出：[[12,21,16],[27,45,33],[24,39,28]]

示例 2：

输入：mat = [[1,2,3],[4,5,6],[7,8,9]], k = 2
输出：[[45,45,45],[45,45,45],[45,45,45]]

解法:
算法思路:
二维前缀和的简单应用题，关键就是我们在填写结果矩阵的时候，要找到原矩阵对应区域的「左上角」以及「右下角」的坐标(推荐大家画图)
左上角坐标:x1 = i-k，y1 =j-k，但是由于会「超过矩阵」的范围，因此需要对0取个 max。
因此修正后的坐标为:x1=max(0，i-k)，y1= max(0，j- k)。
右下角坐标: x1 = i + k，y1 = j+k，但是由于会「超过矩阵」的范围，因此需要对 m-1，以及n-1取一个 min。因此修正后的坐标为:x2= min(m-1，i+ k)，y2 = min(n-1,j+ k)。
然后将求出来的坐标代入到「二维前缀和矩阵」的计算公式上即可~(但是要注意下标的映射关系).

class Solution {
public:
    vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) 
    {
        int m=mat.size();
        int n=mat[0].size();

        vector<vector<int>> dp(m+1,vector<int>(n+1));
        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];
            }
        }
        vector<vector<int>> ret(m,vector<int>(n));
        for(int i=0;i<m;i++)//使用
        {
            for(int j=0;j<n;j++)
            {
                int x1=max(0,i-k)+1,x2=min(m-1,i+k)+1;
                int y1=max(0,j-k)+1,y2=min(n-1,j+k)+1;

                ret[i][j]=dp[x2][y2]-dp[x1-1][y2]-dp[x2][y1-1]+dp[x1-1][y1-1];
            }
        }
        return ret;
    }
};