当前位置：首页 > news >正文

算法-前缀和与差分

news 来源：原创 2025/7/13 5:45:37

一、前缀和（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]

一维前缀和

定义对于给定的数列，其前缀和数列定义为，并且规定。例如数列，，，，。
计算方法 可以通过递推方式计算前缀和，即。在 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=147258369

构建前缀和矩阵 prefixSum：

[13651221122745]15123122762145

查询子矩阵 (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，原矩阵此处有误，实际应为正确计算)

四、应用场景

高频子矩阵和查询（如 LeetCode 304. 二维区域和检索）。
图像处理：计算图像局部区域的像素和。
动态规划优化：在二维动态规划问题中减少重复计算。

五、复杂度分析

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

六、注意事项

索引边界：矩阵的行列索引需从 0 开始，避免越界。
空矩阵处理：输入矩阵为空时需返回异常或合理值。
大数溢出：若元素值较大，前缀和可能溢出，需使用 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 的「航班预订统计」「拼车」问题）。以下是差分算法的完整解析：

一、核心思想

差分数组定义
给定原数组 nums，其差分数组 diff 满足：
- diff[0] = nums[0]
- diff[i] = nums[i] - nums[i-1]（当 i > 0 时）
区间操作优化
对原数组的区间 [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。

四、应用场景

高频区间更新
例如多次对数组的某个区间进行增减操作，时间复杂度从 O(kn) 优化到 O(n + k)，其中 k 是操作次数
动态维护数组状态
例如游戏中多个区域同时施加增益/减益效果。

五、复杂度分析

操作	时间复杂度	空间复杂度
构建差分数组	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]}
}

七、注意事项

索引边界：注意 right + 1 是否超出数组范围（避免越界）。
初始数组处理：原数组为空时需特殊处理。
多次更新：可连续调用 rangeUpdate，最后统一还原数组。

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

一、前缀和（Prefix Sum）

1. 核心思想

2. 定义

3. 代码实现

4. 应用场景

5. 示例

一维前缀和

二维前缀和详解

一、核心思想

二、实现步骤

1. 构建二维前缀和数组

2. 查询子矩阵和

三、示例演示

四、应用场景

五、复杂度分析

六、注意事项

七、完整代码示例

差分算法详解

一、核心思想

二、实现步骤

1. 构建差分数组

2. 区间增减操作

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

三、示例演示

四、应用场景

五、复杂度分析

六、完整代码示例

七、注意事项

相关文章：