【算法】【优选算法】前缀和（上）

目录

• 一、前缀和算法简介
• • 1.1 一维前缀和模版
  • 1.2 二位前缀和模版
• 二、【模板】前缀和
• • 2.1 前缀和
  • 2.2 暴力枚举
• 三、【模板】⼆维前缀和
• • 3.1 前缀和
  • 3.2 暴力枚举
• 四、724.寻找数组的中⼼下标
• • 4.1 前缀和
  • 4.2 暴力枚举
• 五、238.除⾃⾝以外数组的乘积
• • 5.1 前缀和
  • 5.2 暴力枚举

一、前缀和算法简介

前缀和算法：就是快速求取数组中一段连续区间的和的算法。

1.1 一维前缀和模版

• 预处理一个前缀和数组dp[ ]：数组中的元素dp[ i ]表示从原数组[ 1 , i ]的和。
• 所以 dp[ i ] = dp [ i - 1 ] + arr[ i ]
• 要求区间[ l , r ] 的和，就是dp[ r ] - dp[ l - 1 ]

1.2 二位前缀和模版

• 预处理一个前缀和矩阵：dp[ i ][ j ]的含义就是从原数组(1,1)到(i , j)的和。
• 我们求dp[ i ][ j ] : dp[ i ][ j ] = dp[ i - 1][ j ] + dp[ i ][ j - 1] - dp[ i - 1][ j - 1] + arr[ i ][ j ]。就相当于下图的：B区 + C区 - A区 + arr[ i ][ j ]
  
• 求(x1,y1)到(x2,y2)的和：dp[x2][y2] - dp[x1-1][y2] - dp[x2][y1-1] + dp[x1-1][y1-1]。对应下图就是: B区 - C区 - D区 + A区
  

二、【模板】前缀和

题目链接：【模板】前缀和

题目描述：

题目解析：

• 给我们一个数组从1下标开始给数组元素，让我们打印出要求的每一段子数组和。

2.1 前缀和

解题思路：

• 我们使用一个一个dp数组来表示每一段数组的和。即dp[ i ] 就表示原数组中1到 i 下标元素的和。
• 求l到r的元素和，直接就是dp[ r ] - dp[ l - 1]。
• 由于可能求0到2这种 l 等于0的子数组，所以我们将dp数组的长度置为n+1，并且dp[ 0 ] = 0。
• 细节问题：由于元素值是比较大的，所以我们求和是有可能超出int范围的，所以dp数组要使用long类型。

解题代码：

//时间复杂度：O(n+q)//空间复杂度：O(n)import java.util.Scanner;public class Main {  public static void main(String[] args) {  Scanner in = new Scanner(System.in); int n = in.nextInt(); int q = in.nextInt(); long[] dp = new long[n+1]; for(int i = 1; i <= n; i++) {  dp[i] = dp[i-1] + (long)in.nextInt(); } while(q > 0) {  int l = in.nextInt(); int r = in.nextInt(); System.out.println(dp[r] - dp[l-1]); q--; } }}

2.2 暴力枚举

解题思路：

• 直接先将数组存下来，在通过 l 和 r来遍历求和。
• 会超时。

解题代码：

//时间复杂度：O(n*q)//空间复杂度：O(1)import java.util.Scanner;public class Main {  public static void main(String[] args) {  Scanner in = new Scanner(System.in); int n = in.nextInt(); int q = in.nextInt(); int[] arr = new int[n+1]; for(int i = 1