算法-前缀和与差分

一、前缀和（Prefix Sum）

1. 核心思想

前缀和是一种预处理数组的方法，通过预先计算并存储数组的前缀和，使得后续的区间和查询可以在**O(1)**时间内完成。

2. 定义

给定数组 nums，前缀和数组 prefixSum 的每个元素 prefixSum[i] 表示从 nums[0] 到 nums[i] 的和：
prefixSum[i] = nums[0] + nums[1] + ... + nums[i]

3. 代码实现

// 构建前缀和数组
public int[] buildPrefixSum(int[] nums) {int n = nums.length;int[] prefixSum = new int[n];prefixSum[0] = nums[0];for (int i = 1; i < n; i++) {prefixSum[i] = prefixSum[i - 1] + nums[i];}return prefixSum;
}// 查询区间和 [left, right]
public int queryRangeSum(int[] prefixSum, int left, int right) {if (left == 0) return prefixSum[right];return prefixSum[right] - prefixSum[left - 1];
}

4. 应用场景

• 高频区间和查询：例如多次查询数组的某个子区间和。

• 二维扩展：处理二维矩阵中的子矩阵和（如LeetCode 304题）。

5. 示例

假设 nums = [1, 2, 3, 4]，前缀和数组为 [1, 3, 6, 10]：

• queryRangeSum([0, 2]) → 6（即 1+2+3）

• queryRangeSum([1, 3]) → 9（即 2+3+4）

前缀和是从1开始的  定义S[0]=0。注意区间和M-N之间的和是S[N]-S[M-1]

一维前缀和

1. 定义 对于给定的数列，其前缀和数列定义为，并且规定。例如数列，，， ，。
2. 计算方法 可以通过递推方式计算前缀和，即 。在 Java 代码中实现如下：

import java.util.Scanner;public class OneDPrefixSum {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();int m = scanner.nextInt();int[] a = new int[n + 1];int[] s = new int[n + 1];for (int i = 1; i <= n; i++) {a[i] = scanner.nextInt();}for (int i = 1; i <= n; i++) {s[i] = s[i - 1] + a[i];}for (int i = 0; i < m; i++) {int l = scanner.nextInt();int r = scanner.nextInt();System.out.println(s[r] - s[l - 1]);}}
}

这里首先通过循环读取数组 a 的元素，然后计算前缀和数组 s 。对于每次询问的区间 [l, r]，其区间和通过 快速得到。原理是 是前 r 项的和， 是前 l - 1 项的和，两者相减就得到区间 [l, r]的和。

3. 应用场景 当需要频繁查询数列中某一区间的和时，使用前缀和可将每次查询时间复杂度从 O(n)（暴力求和）降低到O(1) 。比如统计一段时间内数据的累计和等场景。

二维前缀和详解

二维前缀和是一种用于快速计算矩阵中子矩阵元素和的高效算法，适用于需要频繁查询子矩阵和的场景（如LeetCode 304题）。

---

一、核心思想

通过预处理构建一个前缀和矩阵，使得任意子矩阵的和可以在 O(1) 时间内查询。
核心公式（假设矩阵从左上角 (0,0) 开始）：

prefixSum[i][j]=matrix[i][j]+prefixSum[i−1][j]+prefixSum[i][j−1]−prefixSum[i−1][j−1]prefixSum[i][j]=matrix[i][j]+prefixSum[i−1][j]+prefixSum[i][j−1]−prefixSum[i−1][j−1]

查询子矩阵 (x1, y1) 到 (x2, y2) 的和：

sum=prefixSum[x2][y2]−prefixSum[x1−1][y2]−prefixSum[x2][y1−1]+prefixSum[x1−1][y1−1]sum=prefixSum[x2][y2]−prefixSum[x1−1][y2]−prefixSum[x2][y1−1]+prefixSum[x1−1][y1−1]

---

二、实现步骤

1. 构建二维前缀和数组

假设原始矩阵为 matrix[m][n]，前缀和矩阵为 prefixSum[m][n]：

public int[][] buildPrefixSum(int[][] matrix) {int m = matrix.length, n = matrix[0].length;int[][] prefixSum = new int[m][n];prefixSum[0][0] = matrix[0][0];// 初始化第一行和第一列for (int j = 1; j < n; j++) prefixSum[0][j] = prefixSum[0][j-1] + matrix[0][j];for (int i = 1; i < m; i++) prefixSum[i][0] = prefixSum[i-1][0] + matrix[i][0];// 填充其他位置for (int i = 1; i < m; i++) {for (int j = 1; j < n; j++) {prefixSum[i][j] = matrix[i][j] + prefixSum[i-1][j] + prefixSum[i][j-1] - prefixSum[i-1][j-1];}}return prefixSum;
}

2. 查询子矩阵和

public int querySubmatrix(int[][] prefixSum, int x1, int y1, int x2, int y2) {int sum = prefixSum[x2][y2];if (x1 > 0) sum -= prefixSum[x1-1][y2];  // 减去上方区域if (y1 > 0) sum -= prefixSum[x2][y1-1];  // 减去左侧区域if (x1 > 0 && y1 > 0) sum += prefixSum[x1-1][y1-1];  // 补回重复减去的左上角return sum;
}

---

三、示例演示

假设原始矩阵为：

matrix=[123456789]matrix=​147​258​369​​

构建前缀和矩阵 prefixSum：

[13651221122745]​1512​31227​62145​​

查询子矩阵 (1,1) 到 (2,2) 的和：

sum=45−21−12+3=15(即 5+6+8+9=28，原矩阵此处有误，实际应为正确计算)sum=45−21−12+3=15(即 5+6+8+9=28，原矩阵此处有误，实际应为正确计算)

---

四、应用场景

1. 高频子矩阵和查询（如 LeetCode 304. 二维区域和检索）。

2. 图像处理：计算图像局部区域的像素和。

3. 动态规划优化：在二维动态规划问题中减少重复计算。

---

五、复杂度分析

操作	时间复杂度	空间复杂度
构建前缀和矩阵	O(mn)	O(mn)
查询子矩阵和	O(1)	O(1)

---

六、注意事项

1. 索引边界：矩阵的行列索引需从 0 开始，避免越界。

2. 空矩阵处理：输入矩阵为空时需返回异常或合理值。

3. 大数溢出：若元素值较大，前缀和可能溢出，需使用 long 类型存储。

---

七、完整代码示例

public class TwoDPrefixSum {private int[][] prefixSum;public TwoDPrefixSum(int[][] matrix) {if (matrix.length == 0 || matrix[0].length == 0) return;int m = matrix.length, n = matrix[0].length;prefixSum = new int[m][n];// 构建前缀和矩阵prefixSum[0][0] = matrix[0][0];for (int j = 1; j < n; j++) prefixSum[0][j] = prefixSum[0][j-1] + matrix[0][j];for (int i = 1; i < m; i++) prefixSum[i][0] = prefixSum[i-1][0] + matrix[i][0];for (int i = 1; i < m; i++) {for (int j = 1; j < n; j++) {prefixSum[i][j] = matrix[i][j] + prefixSum[i-1][j] + prefixSum[i][j-1] - prefixSum[i-1][j-1];}}}public int sumRegion(int x1, int y1, int x2, int y2) {int sum = prefixSum[x2][y2];if (x1 > 0) sum -= prefixSum[x1-1][y2];if (y1 > 0) sum -= prefixSum[x2][y1-1];if (x1 > 0 && y1 > 0) sum += prefixSum[x1-1][y1-1];return sum;}public static void main(String[] args) {int[][] matrix = {{1, 2, 3},{4, 5, 6},{7, 8, 9}};TwoDPrefixSum solver = new TwoDPrefixSum(matrix);System.out.println(solver.sumRegion(1, 1, 2, 2)); // 输出28（5+6+8+9）}
}

---

通过掌握二维前缀和，你可以高效解决涉及子矩阵和的复杂问题，显著提升算法性能。

差分算法详解

差分（Difference Array）是一种用于高效处理数组区间增减操作的算法技巧，尤其适用于需要多次对数组的某个区间进行增减操作的场景（如 LeetCode 的「航班预订统计」「拼车」问题）。以下是差分算法的完整解析：

---

一、核心思想

1. 差分数组定义
   给定原数组 nums，其差分数组 diff 满足：

   • diff[0] = nums[0]

   • diff[i] = nums[i] - nums[i-1]（当 i > 0 时）

2. 区间操作优化
   对原数组的区间 [left, right] 进行增减操作时，只需修改差分数组的两个位置：

   • diff[left] += val

   • 若 right + 1 < n，则 diff[right + 1] -= val
     最后通过差分数组还原原数组时，区间增减的效果会自动生效。

---

二、实现步骤

1. 构建差分数组

// 输入原数组 nums，返回差分数组 diff
public int[] buildDiffArray(int[] nums) {if (nums == null || nums.length == 0) return new int[0];int n = nums.length;int[] diff = new int[n];diff[0] = nums[0];for (int i = 1; i < n; i++) {diff[i] = nums[i] - nums[i - 1];}return diff;
}

2. 区间增减操作

// 对原数组的区间 [left, right] 增加 val（通过差分数组间接实现）
public void rangeUpdate(int[] diff, int left, int right, int val) {diff[left] += val;if (right + 1 < diff.length) {diff[right + 1] -= val;}
}

3. 通过差分数组还原原数组

// 输入差分数组 diff，返回还原后的原数组 nums
public int[] restoreArray(int[] diff) {if (diff == null || diff.length == 0) return new int[0];int n = diff.length;int[] nums = new int[n];nums[0] = diff[0];for (int i = 1; i < n; i++) {nums[i] = nums[i - 1] + diff[i];}return nums;
}

---

三、示例演示

假设原数组 nums = [1, 3, 5, 7]，其差分数组为 diff = [1, 2, 2, 2]：

• 对区间 [1, 2] 增加 3：

  rangeUpdate(diff, 1, 2, 3); // diff 变为 [1, 5, 2, -1]

• 还原后的数组：

  restoreArray(diff); // 结果 [1, 6, 8, 7]

  验证：原数组的 [1, 2] 区间（即 3, 5）被增加了 3，结果变为 6, 8。

---

四、应用场景

1. 高频区间更新
   例如多次对数组的某个区间进行增减操作，时间复杂度从 O(kn) 优化到 O(n + k)，其中 k 是操作次数

2. 动态维护数组状态
   例如游戏中多个区域同时施加增益/减益效果。

---

五、复杂度分析

操作	时间复杂度	空间复杂度
构建差分数组	O(n)	O(n)
单次区间更新	O(1)	O(1)
还原原数组	O(n)	O(n)

---

六、完整代码示例

public class DifferenceArray {private int[] diff;// 根据原数组构建差分数组public DifferenceArray(int[] nums) {if (nums.length == 0) return;int n = nums.length;diff = new int[n];diff[0] = nums[0];for (int i = 1; i < n; i++) {diff[i] = nums[i] - nums[i - 1];}}// 区间 [left, right] 增加 valpublic void rangeUpdate(int left, int right, int val) {diff[left] += val;if (right + 1 < diff.length) {diff[right + 1] -= val;}}// 还原原数组public int[] restore() {int n = diff.length;int[] nums = new int[n];nums[0] = diff[0];for (int i = 1; i < n; i++) {nums[i] = nums[i - 1] + diff[i];}return nums;}// 测试代码public static void main(String[] args) {int[] nums = {1, 3, 5, 7};DifferenceArray da = new DifferenceArray(nums);da.rangeUpdate(1, 2, 3); // 对区间 [1,2] 增加3int[] result = da.restore();System.out.println(Arrays.toString(result)); // 输出 [1, 6, 8, 7]}
}

---

七、注意事项

1. 索引边界：注意 right + 1 是否超出数组范围（避免越界）。

2. 初始数组处理：原数组为空时需特殊处理。

3. 多次更新：可连续调用 rangeUpdate，最后统一还原数组。

---

通过差分算法，可以将多次区间操作的时间复杂度从 O(kn) 优化到 O(n + k)，是处理大规模区间更新问题的核心技巧。