前缀和与差分：从一维到二维的高效数据操作技巧（Java版）

前缀和与差分：从一维到二维的高效数据操作技巧（Java版）

前缀和与差分是算法中经典的数据预处理技巧，能将数组/矩阵的区间查询、区间修改时间复杂度从O ( n ) O(n)O(n)/O ( n m ) O(nm)O(nm)优化到O ( 1 ) O(1)O(1)，是刷题和工程开发中处理区间问题的“利器”。本文从一维到二维，结合Java实战代码，拆解核心逻辑与应用场景。

推荐视频：

前缀和与差分视频【共四集视频】

一、一维前缀和：快速查区间和

题目描述：给定长度为 n的数组，有 q次查询，每次查询区间 [L,R]的元素和，请输出每次查询结果。

核心思想

前缀和数组preSum中，preSum[i]表示原数组前i个元素的和。通过预处理前缀和，任意区间[L, R]的和可通过preSum[R] - preSum[L-1]直接计算（索引从1开始，避免边界处理）。

图片解释

一维前缀和：文字版分解动画

核心Java代码

importjava.util.Scanner;// 一维前缀和核心实现（索引1开始）publicclassPrefixSum1D{publicstaticvoidmain(String[]args){Scannersc=newScanner(System.in);intn=sc.nextInt();// 数组长度intq=sc.nextInt();// 查询次数int[]arr=newint[n+1];// 原数组（1-based）// 输入原数组for(inti=1;i<=n;i++){arr[i]=sc.nextInt();}// 构建前缀和数组int[]preSum=newint[n+1];for(inti=1;i<=n;i++){preSum[i]=preSum[i-1]+arr[i];}// 处理查询for(inti=0;i<q;i++){intL=sc.nextInt();intR=sc.nextInt();intsum=preSum[R]-preSum[L-1];System.out.println(sum);}sc.close();}}

适用场景

• 多次查询数组子区间和（如成绩区间总分、子数组和统计）

二、一维差分：快速改区间值

题目描述：给定初始全 0 的数组，有 m次操作，每次操作对区间 [L,R]加 k，操作完成后输出最终数组。

核心思想

差分是前缀和的逆运算，差分数组diff标记区间修改的“起点”和“终点”：对[L, R]加k，只需diff[L] += k、diff[R+1] -= k（多开一位避免越界），最后对diff求前缀和即可还原修改后的数组。

图片解释

原理：

因为差分数组中，标记位加了一个数还原成原数组的时候，后面的数都会累加，然后在R+1位再减去这个数停止累加！！！

一维差分：文字版分解动画

核心Java代码

// 一维差分核心实现（索引1开始）importjava.util.Arrays;importjava.util.Scanner;publicclassDifference1D{publicstaticvoidmain(String[]args){Scannersc=newScanner(System.in);intn=sc.nextInt();// 数组长度intm=sc.nextInt();// 操作次数int[]diff=newint[n+2];// 差分数组（多开1位避免越界）// 处理区间修改操作for(inti=0;i<m;i++){intL=sc.nextInt();intR=sc.nextInt();intk=sc.nextInt();diff[L]+=k;diff[R+1]-=k;}// 还原数组（对差分数组求前缀和）int[]res=newint[n];intcur=0;for(inti=1;i<=n;i++){cur+=diff[i];res[i-1]=cur;}// 输出结果System.out.println(Arrays.toString(res).replaceAll("[\\[\\],]",""));sc.close();}}

适用场景

• 多次批量修改数组区间值（如区间加减、数据批量更新）
• 蓝桥杯常考：结合差分解决 “区间操作后统计数组特征”（如最大值、平均值）。

三、二维前缀和：快速查矩阵子矩形和

题目描述：给定 n×m 的矩阵，有 q次查询，每次查询子矩形 [(x1,y1),(x2,y2)]的元素和，请输出每次查询结果。

核心思想

二维前缀和数组preSum[i][j]表示以(1,1)为左上角、(i,j)为右下角的矩形和。递推公式需补偿重复累加的区域，子矩形和通过“大减小、加补偿”计算。

图片解释

二维前缀和：文字版分解动画

核心Java代码

importjava.util.Scanner;// 二维前缀和核心实现（索引1开始）publicclassPrefixSum2D{publicstaticvoidmain(String[]args){Scannersc=newScanner(System.in);intn=sc.nextInt();// 行数intm=sc.nextInt();// 列数intq=sc.nextInt();// 查询次数// 输入矩阵（1-based）int[][]matrix=newint[n+1][m+1];for(inti=1;i<=n;i++){for(intj=1;j<=m;j++){matrix[i][j]=sc.nextInt();}}// 构建二维前缀和数组int[][]preSum=newint[n+1][m+1];for(inti=1;i<=n;i++){for(intj=1;j<=m;j++){preSum[i][j]=preSum[i-1][j]+preSum[i][j-1]-preSum[i-1][j-1]+matrix[i][j];}}// 处理查询for(inti=0;i<q;i++){intx1=sc.nextInt();inty1=sc.nextInt();intx2=sc.nextInt();inty2=sc.nextInt();// 子矩形和公式：大减小 + 补偿intsum=preSum[x2][y2]-preSum[x1-1][y2]-preSum[x2][y1-1]+preSum[x1-1][y1-1];System.out.println(sum);}sc.close();}}

适用场景

• 矩阵子区域和查询（如图像局部亮度统计、二维数据区间分析）；
• 蓝桥杯常考：结合二维前缀和解决 “矩阵中子矩形满足条件的数量”“最大子矩形和” 等问题。

四、二维差分：快速改矩阵子矩形值

题目描述：给定初始全 0 的 n×m矩阵，有 k 次操作，每次操作对子矩形 [(x1,y1),(x2,y2)] 加 val，操作完成后输出最终矩阵。

核心思想

二维差分通过4个标记点实现子矩形批量修改：对(x1,y1)-(x2,y2)加k，只需修改diff[x1][y1]、diff[x1][y2+1]、diff[x2+1][y1]、diff[x2+1][y2+1]，最后对diff求二维前缀和还原矩阵。

图片解释

二维差分：文字版分解动画

核心Java代码

importjava.util.Scanner;// 二维差分核心实现（索引1开始）publicclassDifference2D{publicstaticvoidmain(String[]args){Scannersc=newScanner(System.in);intn=sc.nextInt();// 行数intm=sc.nextInt();// 列数intk=sc.nextInt();// 操作次数// 差分数组（多开1行1列，避免越界）int[][]diff=newint[n+2][m+2];// 处理子矩形修改操作for(inti=0;i<k;i++){intx1=sc.nextInt();inty1=sc.nextInt();intx2=sc.nextInt();inty2=sc.nextInt();intval=sc.nextInt();// 二维差分4个标记点diff[x1][y1]+=val;diff[x1][y2+1]-=val;diff[x2+1][y1]-=val;diff[x2+1][y2+1]+=val;}// 还原矩阵（对差分数组求二维前缀和）int[][]res=newint[n+1][m+1];for(inti=1;i<=n;i++){for(intj=1;j<=m;j++){// 求前缀和res[i][j]=res[i-1][j]+res[i][j-1]-res[i-1][j-1]+diff[i][j];// 输出当前行（去掉最后一列的空格）System.out.print(res[i][j]+(j==m?"\n":" "));}}sc.close();}}

适用场景

• 矩阵子区域批量修改（如图像局部调色、二维数据批量更新）；
• 蓝桥杯常考：结合二维差分解决 “多次矩阵区间操作后统计极值”“矩阵操作后满足条件的子矩形数量” 等问题。

五、核心总结

关键注意点

1. 索引建议从1开始，避免边界越界问题；
2. 差分操作后必须通过前缀和还原数组/矩阵；
3. 二维前缀和/差分需注意“重复区域补偿”逻辑。