优选算法的睿智之林：前缀和专题(一)

专栏：算法的魔法世界

个人主页：手握风云

目录

一、前缀和

二、例题讲解

2.1. 一维前缀和

2.2. 二维前缀和

2.3. 寻找数组的中心下标

2.4. 除自身以外数组的乘积

---

一、前缀和

        前缀和算法是一种用于处理数组或序列数据的算法，其核心思想是通过预先计算出数组中每个位置之前所有元素的和（即前缀和），从而快速解决一些与区间和相关的问题。它在处理数组求和、区间统计等场景下非常高效。

二、例题讲解

2.1. 一维前缀和

        我们需要注意一个细节，上面题目的数组给定下标是从1开始的。我们先来想一个暴力解法——模拟。每次查询都从l下标一直遍历到r下标，最坏情况下就是q次都是从头遍历到尾，所以暴力解法的时间复杂度为，n、q的最大值都为，一定会超时。

        第二种解法就是利用前缀和算法。第一步，我们先预处理出一个前缀和数组int[] dp，dp[i]代表的是arr数组区间[1,i]的和。而数组dp中每一个元素的算法不用再从头加到尾，直接利用递推公式dp[i] = dp[i-1] + arr[i]。

        第二步是利用前缀和数组。比如我们要计算[2,5]区间的和，我们没必要直接访问下标2——5。根据下图可以得出，dp[r] - dp[l-1]。我们预处理前缀和的时间复杂度为，每次查询可以直接获取下标，那么q次查询的时间复杂度为，整体时间复杂度为。

        前面提到了一个细节，就是数组下标为什么要从1开始？如果我们要查询[0,2]区间的和，那么l-1就会为-1，就会无法访问到数组的第一个元素，从而方便处理边界问题。

        完整代码实现：

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);while (in.hasNextInt()) {int n = in.nextInt(), q = in.nextInt();int[] arr = new int[n + 1];for (int i = 1; i < n + 1; i++) {arr[i] = in.nextInt();}//预处理一个前缀和数组long[] dp = new long[n + 1];for (int i = 1; i < n + 1; i++) {dp[i] = dp[i - 1] + arr[i];}//使用前缀和数组while (q > 0) {int l = in.nextInt(), r = in.nextInt();System.out.println(dp[r] - dp[l - 1]);q--;}}}
}

2.2. 二维前缀和

        暴力解法与上一道题一样，也是利用模拟在指定区间内遍历，时间复杂度为。跟上一道题一样，也是会超时的。

        同一维前缀和一样，我们第一步还是先预处理一个与给定矩阵arr[][]同等规模的前缀和矩阵。dp[i][j]里的每个元素代表着矩阵arr[][]的阴影面积。

        关于如何求出dp[i][j]的值，我们没有必要再去遍历矩阵arr，因为遍历的时间复杂度会与暴力求解的一样高。我们可以利用完全平方公式的思想，下图中的元素之和，就是四个区域A、B、C、D的和。A区域的和可以很好的算出来：dp[i-1][j-1]，但是B、C区域的和又不好算了。我们退而求其次，利用A+B+A+C-A的来算。A+B：dp[i-1][j]；A+C：dp[i][j-1]。

        第二步就是利用二维前缀和矩阵。题目要求我们算出(x1,y1)——(x2,y2)里面的值直接A+B+C+D-(A+B)-(A+C)+A求出结果。

        完整代码实现：

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);//1. 读取输入的数据int n = in.nextInt(), m = in.nextInt(), q = in.nextInt();int[][] arr = new int[n + 1][m + 1];for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {arr[i][j] = in.nextInt();}}//2. 预处理一个前缀和矩阵long[][] dp = new long[n + 1][m + 1];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];}}//3. 使用前缀和矩阵while (q-- > 0) {int x1 = in.nextInt(), y1 = in.nextInt(), x2 = in.nextInt(), y2 = in.nextInt();System.out.println(dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1]);}}
}

2.3. 寻找数组的中心下标

        本题是要我们查找一个下标，这个下标左侧的元素之和与右侧的元素之和相等。如果存在这样一个下标则返回这个下标值，如果没有返回-1。

        我们先来思考暴力解法。枚举每一个下标，计算左侧的元素之和与右侧的元素之和是否相等。我们需要从头到尾遍历数组下标，再去遍历左侧和右侧的元素，所以时间复杂度为。

        接下来对暴力解法进行优化。我们需要求的是某段数组元素的和，那么就可以利用前缀和思想，i左侧的元素之和f(i) = f(i-1) + nums[i-1]，i右侧的元素之和g(i) = g(i+1) + nums[i+1]。只要比较出f(i) = g(i)，就返回i。

        还有一些细节：1. 防止数组越界访问，如果i=0，那么f(i-1)就是[-1,0]这段区间的和，f(0)=0；同理，g(n-1)=0。2. f是依赖与i-1，所以f数组是从左向右填写；g是依赖于i+1，所以g数组是从右向左填写的。

        完整代码实现：

public class Solution {public int pivotIndex(int[] nums) {int n = nums.length;int[] f = new int[n];int[] g = new int[n];//预处理前缀和数组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;}
}

2.4. 除自身以外数组的乘积

        暴力解法与上一题类似，枚举数组下标，再遍历下标的左右两侧计算乘积。时间复杂度也与上一题一样，也是。

        利用前缀和的思想，预处理出i左侧区间的乘积和右侧区间的乘积，到某个下标时，直接从前缀与后缀里进行拿值就可以。算法原理与上一题完全一样的，只不过这道题是要求乘积。前缀积f[i] = f[i - 1] * nums[i - 1]；g[i] = g[i+1] * nums[i+1]。细节处理上，与上一题不同的是，边界f[0]与g[n-1]要赋值成1。

        完整代码实现：

public class Solution {public int[] productExceptSelf(int[] nums) {int n = nums.length;int[] f = new int[n];int[] g = new int[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];int[] ret = new int[n];for (int i = 0; i < n; i++)ret[i] = f[i] * g[i];return ret;}
}