优选算法的睿智之林：前缀和专题(一)
专栏：算法的魔法世界
个人主页：手握风云
目录
一、前缀和
二、例题讲解
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;
}
}