前缀和（Prefix Sum）

什么是前缀和算法前缀和是一种预处理技术用于快速计算数组中任意区间的元素和。核心思想是预先计算从数组开头到每个位置的累积和之后任意区间[i, j]的和都可以通过prefix[j] - prefix[i-1]在 O(1) 时间内得到。算法图解一维数组前缀和原始数组 nums: [3, 1, 4, 1, 5, 9, 2, 6] 索引: 0 1 2 3 4 5 6 7 前缀和 prefix: [3, 4, 8, 9, 14, 23, 25, 31] ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ 0~0 0~1 0~2 0~3 0~4 0~5 0~6 0~7 计算过程 prefix[0] 3 prefix[1] 3 1 4 prefix[2] 4 4 8 prefix[3] 8 1 9 ...以此类推区间查询图解查询 nums[2..5] 的和即 4159 19 prefix[5] 314159 23 (0~5的和) prefix[1] 31 4 (0~1的和) 结果 prefix[5] - prefix[1] 23 - 4 19 ✓ 图示 [3, 1, 4, 1, 5, 9, 2, 6] 0 1 2 3 4 5 6 7 ↑--------↑ 我们要的区间 整体(0~5) - 前缀(0~1)Java 实现代码1. 基础一维前缀和publicclassPrefixSum1D{// 构建前缀和数组publicstaticint[]buildPrefixSum(int[]nums){intnnums.length;int[]prefixnewint[n];prefix[0]nums[0];for(inti1;in;i){prefix[i]prefix[i-1]nums[i];}returnprefix;}// 查询区间 [left, right] 的和闭区间publicstaticintrangeSum(int[]prefix,intleft,intright){if(left0){returnprefix[right];}returnprefix[right]-prefix[left-1];}// 测试publicstaticvoidmain(String[]args){int[]nums{3,1,4,1,5,9,2,6};int[]prefixbuildPrefixSum(nums);System.out.println(原始数组: java.util.Arrays.toString(nums));System.out.println(前缀和数组: java.util.Arrays.toString(prefix));// 查询多个区间System.out.println(\n区间 [2, 5] 的和: rangeSum(prefix,2,5));// 19System.out.println(区间 [0, 3] 的和: rangeSum(prefix,0,3));// 9System.out.println(区间 [4, 7] 的和: rangeSum(prefix,4,7));// 22}}输出原始数组: [3, 1, 4, 1, 5, 9, 2, 6] 前缀和数组: [3, 4, 8, 9, 14, 23, 25, 31] 区间 [2, 5] 的和: 19 区间 [0, 3] 的和: 9 区间 [4, 7] 的和: 222. 二维矩阵前缀和子矩阵求和publicclassPrefixSum2D{/** * 构建二维前缀和 * prefix[i][j] 表示从 (0,0) 到 (i,j) 的子矩阵和 */publicstaticint[][]buildPrefixSum2D(int[][]matrix){intmmatrix.length;intnmatrix[0].length;int[][]prefixnewint[m][n];for(inti0;im;i){for(intj0;jn;j){prefix[i][j]matrix[i][j];// 加上上方和左方的和减去重复计算的左上角if(i0)prefix[i][j]prefix[i-1][j];if(j0)prefix[i][j]prefix[i][j-1];if(i0j0)prefix[i][j]-prefix[i-1][j-1];}}returnprefix;}/** * 查询子矩阵 [row1,col1] 到 [row2,col2] 的和闭区间 */publicstaticintsubMatrixSum(int[][]prefix,introw1,intcol1,introw2,intcol2){intsumprefix[row2][col2];if(row10)sum-prefix[row1-1][col2];if(col10)sum-prefix[row2][col1-1];if(row10col10)sumprefix[row1-1][col1-1];returnsum;}// 可视化打印矩阵publicstaticvoidprintMatrix(int[][]matrix,Stringtitle){System.out.println(\ntitle:);for(int[]row:matrix){System.out.println(java.util.Arrays.toString(row));}}publicstaticvoidmain(String[]args){int[][]matrix{{1,2,3},{4,5,6},{7,8,9}};printMatrix(matrix,原始矩阵);int[][]prefixbuildPrefixSum2D(matrix);printMatrix(prefix,二维前缀和);// 查询子矩阵 (1,1) 到 (2,2) 的和5689 28System.out.println(\n子矩阵 (1,1) 到 (2,2) 的和: subMatrixSum(prefix,1,1,2,2));// 查询子矩阵 (0,0) 到 (1,2) 的和123456 21System.out.println(子矩阵 (0,0) 到 (1,2) 的和: subMatrixSum(prefix,0,0,1,2));}}输出原始矩阵: [1, 2, 3] [4, 5, 6] [7, 8, 9] 二维前缀和: [1, 3, 6] [5, 12, 21] [12, 27, 45] 子矩阵 (1,1) 到 (2,2) 的和: 28 子矩阵 (0,0) 到 (1,2) 的和: 213. 二维前缀和图解原始矩阵: 前缀和计算过程容斥原理 ┌───┬───┬───┐ prefix[i][j] 当前格 │ 1 │ 2 │ 3 │ 上方prefix[i-1][j] ├───┼───┼───┤ 左方prefix[i][j-1] │ 4 │ 5 │ 6 │ - 左上prefix[i-1][j-1]重复部分 ├───┼───┼───┤ │ 7 │ 8 │ 9 │ └───┴───┴───┘ 子矩阵查询图解以 (1,1) 到 (2,2) 为例 col0 col1 col2 ┌──────┬──────┬──────┐ row0 │ 1 │ 2 │ 3 │ ├──────┼──────┼──────┤ row1 │ 4 │ [5 │ 6 │ ← 目标区域 ├──────┼──────┼──────┤ row2 │ 7 │ 8 │ 9] │ └──────┴──────┴──────┘ 计算prefix[2][2] - prefix[0][2] - prefix[2][0] prefix[0][0] 45 - 6 - 12 1 28 ✓算法复杂度分析操作时间复杂度空间复杂度说明构建前缀和O(n) 或 O(m×n)O(n) 或 O(m×n)一维/二维区间查询O(1)O(1)任意区间单点修改O(n) 或 O(m×n)O(1)需要重建可用树状数组优化四、经典应用场景LeetCode 303- 区域和检索一维LeetCode 304- 二维区域和检索LeetCode 560- 和为 K 的子数组配合哈希表图像处理- 积分图快速计算特征子数组求和- 快速计算任意区间和子矩阵求和- 图像处理、游戏地图差分数组- 区间修改前缀和的逆运算前缀和是算法竞赛和工程开发中非常实用的技巧能将区间查询从 O(n) 优化到 O(1)特别适合查询频繁、修改较少的场景。