【ONE·基础算法 || 前缀和】

总言

  主要内容：编程题举例，理解前缀和的思想。

文章目录

• 总言
• 1、前缀和
• 2、【模板】一维前缀和（easy）
• • 2.1、如何理解一维数组前缀和
  • 2.2、题解
• 3、【模板】二维前缀和（medium）
• • 3.1、如何理解二维数组前缀和
  • 3.2、题解
• 4、寻找数组的中心下标（easy）
• • 4.1、题解
• 5、除自身以外数组的乘积（medium）
• • 5.1、题解
• 6、和为 k 的子数组（medium）
• • 6.1、题解
• 7、和可被 K 整除的子数组（medium）
• • 7.1、题解
• 8、连续数组（medium）
• • 8.1、题解
• 9、矩阵区域和（medium）
• • 9.1、题解
• Fin、共勉。

  
  
  
  

1、前缀和

  基本说明： 前缀和算法(Prefix Sum Algorithm)是一种用于高效计算数组前缀和的算法。
  1、这里前缀指数组中某个位置之前（包括该位置）所有元素的和（表明前缀和适用于求一段连续的区间）。
  2、其算法基本思想是通过一次遍历数组，计算每个位置的前缀和，将其存储在一个新的数组中。然后便可通过查询新数组中的元素，快速计算出任意子数组的和，从而无需重新遍历原数组。因此，在处理大型数组或需要频繁计算子序列和的问题时，前缀和算法非常有用。
  
  
  以下前两题将具体展开说明一维数组的前缀和以及二维数组的前缀和。
  
  

2、【模板】一维前缀和（easy）

  题源：链接。

  
  

2.1、如何理解一维数组前缀和

  1）、暴力解法
  根据题目，暴力解法即遍历数组（$q$次），求出每次指定的 $[l，r]$ 此段区间内的元素和：$a_l+a_{l+1}+\dots \dots +a_{r-1}+ar$。

  如上述示例， a = { 1 ， 2 ， 4 } ， a=\{1，2，4\}， a={1，2，4}，$q=2。$
  首次 $[l，r]$ 为 $[1，2]，$ 即求 $a_1+a_2=3$；
  第二次$[l，r]$ 为 $[2，3]，$ 即求 $a_2+a_3=6$。

  按照这种操作，时间复杂度为$O(q\ast n)$，q次循环，每次遍历元素个数为n。
  
  
  
  2）、一维数组前缀和

  步骤：①预处理出来一个前缀和数组；②使用前缀和数组。
  
  

  ①预处理前缀和数组： 对于一个给定的数组 $arr$ ，它的前缀和数组 $dp$ 中 $dp[i]$ 表示从第 $1$ 个元素到第 $i$ 个元素的总和。计算公式如下：

$$dp[i]=dp[i-1]+arr[i]$$

  
  ②使用前缀和数组： 前缀和主要用于求任意区间的元素之和。计算 $[l，r]$ 区间内的元素之和$arr[l]+arr[l+1]+\dots \dots +arr[r-1]+arr[r]$ ，思路为：
$$dp[r]-dp[l-1]$$
  即：$区间和=前r个元素的和-前l-1个元素的和$。

  
  
  说明1：时间复杂度？
  ①获取缀和数组 $dp$ 需要遍历一遍原数组，此处时间复杂度为 $O(n)$；
  ②求区间 $[l，r]$ 的元素和只用根据公式计算即可，减去了反复多次遍历数组的开销 $O(1)$ ，共有 $q$ 次遍历，则为 $O(1\ast q)$；
  故最终，时间复杂度为：$O(q)+O(n)$

  
  

  说明2：为什么这里下标要从1开始？
  1、从1开始计算前缀和可以确保第一个元素的前缀和就是它本身，这符合前缀和的定义。即前缀和数组的第 $i$ 个元素的值等于原数组中前 $i$ 个元素的和。 如果下标从0开始，那么处理第一个元素时会引入额外的逻辑，因为不存在“前0个元素”的概念。

  2、其次，从$1$开始可以简化计算过程。例如，以下标为 $1$ 开始，求 $[1,2]$，则有 $dp[2]-dp[0]$ ，这里只需要设 $dp[0]=0$ 即可，而这也符合 $dp[2]=arr[1]+arr[2]$ 的特点。

  3、此外，从 $1$ 开始处理下标也便于处理边界情况。 在编程实现中，边界条件往往是最容易出现错误的地方，通过从1开始设置下标，可以避免一些由于下标偏移或越界导致的错误。例如，若下标为 $0$ 开始，$[0,2]$ 则有 $dp[2]-dp[-1]$，越界，需要额外处理。
  
  
  

2.2、题解

  不要死记硬背套用模板，不同题目中可能有微调，因此关键在于理解过程推导。

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

int main() {
    //1、输入
    int n = 0, q = 0;
    cin >> n >> q;
    vector<int> arr(n+1);
    for(int i = 1; i< n+1; ++i)
    {
        cin >> arr[i];
    }

    //2、获取一个预处理数组：含当前位置元素在内的0~i元素和
    vector<long long> dp(n+1);
    for(int i = 1; i< n+1; ++i)
    {
        dp[i] = dp[i-1] + arr[i];
    }

    //3、使用该前缀和数组：查询q次，获取[l,r]元素和
    int l = 0, r = 0;    
    for(int i = 0; i< q;++i)
    {
        cin >> l >> r;
        cout << dp[r] -dp[l-1] << endl;
    }

    return 0;
}

  
  
  
  
  
  

3、【模板】二维前缀和（medium）

  题源：链接

  
  

3.1、如何理解二维数组前缀和

  1）、暴力解法
  因给定了左上角和右下角元素下标，暴力解法下，嵌套两层循环可求出 $(x_1,y_1)-(x_2,y_2)$所含子区间元素和。遍历 $q$ 次即可获取所有结果。$n$ 行 $m$ 列 $q$ 次查询的矩阵，总体时间复杂度为 $O(n\ast m\ast q)$

  
  
  

  2）、二维数组前缀和
    仍旧分为两步骤：①预处理出来一个前缀和数组；②使用前缀和数组。
  
  

  ①预处理出来一个前缀和数组： 给定一个二维数组 $arr$ ，它的前缀和二维数组 $dp$ 中， $dp[i][j]$ 表示以 $(1,1)$ 为左上角元素，以 $(i,j)$ 为右下角元素的矩形块中所有元素的总和。

  要计算每一个$dp[i][j]$，不必每次都遍历求和，有如下换算关系：