前缀和与差分
前缀和与差分常用于处理区间计算和区间修改问题，其核心都是将区间计算转变为单点计算。二者互为逆运算：前缀和负责”快速回答区间查询”——一次区间求和 O(1)；差分负责”快速完成区间修改”——一次区间加减 O(1)，全部修改结束后再花 O(n) 做一次前缀和把原数组整体还原出来。
两个技巧都遵循同一个套路：先花 O(n) 把原数组预处理成一个辅助数组，然后让每一次区间操作都变成只改动辅助数组上的常数个位置。当一道题需要对同一个数组反复进行大量区间查询或区间修改（比如 q 次操作）时，朴素的逐元素遍历总代价是 O(n·q)，而前缀和/差分能把代价降到 O(n + q)，这是最经典、最常用的”空间换时间”优化手段。
一维前缀和
给定数组
a[1..n]，定义前缀和数组S[i] = a[1] + a[2] + … + a[i]，即”从第 1 个元素一直累加到第 i 个元素”的和。预处理（O(n)）： 利用递推式
S[i] = S[i-1] + a[i]从前往后扫一遍即可求出整个 S 数组。同时人为规定S[0] = 0——下标 0 处补一个 0 是重要的边界约定：它让i = 1时递推式依然成立，也让我们查询”从头开始的区间”时无需任何特判。查询（O(1)）： 性质：
a[l..r]的和 =S[r] - S[l-1]，一次查询 O(1)。为什么这个公式成立？把两个前缀和展开：
两式相减，公共部分
a[1..l-1]恰好被抵消，剩下的正好是a[l] + a[l+1] + … + a[r]。也就是说，计算[a,b]的区间和公式为：
a[a] + a[a+1] + a[a+2] + ... + a[b] = S[b] - S[a-1]一次区间求和由 O(区间长度) 降为 O(1)，代价仅仅是在读入数组时顺手把前缀和数组算出来。
注意： 前缀和的前提是原数组在查询期间不再变化。如果一边查询一边修改原数组，前缀和会全部失效，此时要改用下面的差分（只修改、最后查询），或者进一步学习树状数组/线段树等支持动态修改的数据结构。
import java.util.Scanner;public class Main { public static void main(String[] args) { //一维前缀和 Scanner sc = new Scanner(System.in); int n= 10; int[] arr = new int[n]; int[] s = new int[n]; //前缀和从一开始，下标为0的值为0 s[0] = 0; for (int i = 1; i < n; i++) { arr[i] = sc.nextInt(); } for (int i = 1; i < n; i++) { s[i] = s[i-1] + arr[i]; } for (int i = 0; i < n; i++) { System.out.println(s[i]); } int l = 3; int r = 8; //计算数组第三位到第八位的和，时间复杂度为o(1),前缀和数组初始化时间为o(n) System.out.println(s[r] - s[l-1]); }}一维差分
想在原数组
a[l..r]上同时加/减一个值 c，正常做法要逐个修改 r-l+1 个元素，即 O(r-l+1)。引入差分数组
D[i] = a[i] - a[i-1]（规定a[0] = 0）。差分与前缀和互为逆运算：对 D 做一次前缀和，就能把 a 原样还原出来，因为中间项两两抵消，最后只剩
a[i]。区间加 c 只需改两个端点：
为什么只改两个位置就够了？模拟一下”对 D 求前缀和还原 a”的过程：
- 当还原到下标
i < l时，前缀和中还没有累加进D[l]处的 c，这些位置保持不变；- 当
l ≤ i ≤ r时，前缀和中额外多了一个来自D[l]的 c，所以这段区间内的每个元素都被 +c，这正是我们想要修改的区间；- 当
i > r时，D[r+1]处的 -c 开始被累加进来，把之前的 +c 抵消掉，后面的元素恢复原值。举个具体例子：
a = [1,2,3,4,5]（下标 15），差分数组4 位加了 10。D = [1,1,1,1,1]。对区间[2,4]加 10，只需D[2] += 10、D[5] -= 10，D 变为[1,11,1,1,-9]；再求前缀和还原得[1,12,13,14,5]，恰好只有第 2适用场景： 对同一个数组做多次区间修改时，每次修改都只是 O(1) 的端点操作，全部修改完成后再做一次 O(n) 的前缀和还原。m 次修改的总代价是 O(n + m)，远优于朴素的 O(n·m)。
最后做一次前缀和即可还原原数组。
import java.util.Scanner;public class Main { public static void main(String[] args) { //一维差分 Scanner sc = new Scanner(System.in); int[] D = new int[100]; int[] a = new int[100]; for (int i = 0; i < 10; i++) { a[i] = sc.nextInt(); } // 初始化差分数组 for (int i = 1; i <= 10; ++i) D[i] = a[i] - a[i-1]; //将数组第一个到第六个数都加上3 D[1] += 3; D[7] -= 3; // 还原数组 for (int i = 1; i <= 10; ++i) a[i] = a[i-1] + D[i]; for (int i = 0; i < 10; i++) { System.out.println(a[i]); } }}二维差分
二维前缀和：
S[i][j]表示从左上角(1,1)到(i,j)的矩形内所有元素之和。它同样可以用 O(n·m) 递推求出：
S[i][j] = S[i-1][j] + S[i][j-1] - S[i-1][j-1] + a[i][j]，即”上方矩形 + 左方矩形 − 两者重叠的左上矩形 + 自身”。这里减掉一次重叠部分，就是典型的容斥原理：重叠区域被加了两次，所以要减回去一次。查询子矩阵
(x1,y1)到(x2,y2)的和（x1 ≤ x2，y1 ≤ y2）：仍然用容斥理解：先取整个大矩形
(1,1)~(x2,y2)，减去上方多余部分(1,1)~(x1-1,y2)和左方多余部分(1,1)~(x2,y1-1)；此时左上角小矩形(1,1)~(x1-1,y1-1)被减了两次，所以再加回来一次。一次二维区间查询同样是 O(1)。
二维差分： 想把子矩阵
(x1,y1)~(x2,y2)内的所有元素同时加 c，只需修改四个角：可以把它看成”一维差分在二维上的推广”：
D[x1][y1] += c使得求二维前缀和时，目标矩形右下方整个区域都会被加上 c；(x2+1,y1)与(x1,y2+1)处的 -c 分别把目标区域”右方”和”下方”的多余部分截断；而最右下角的(x2+1,y2+1)区域同时被前两个 -c 各减了一次，共减了 2c，所以要再 +c 补回来，使它恢复原值。四个角配合，最终恰好只有目标矩形内 +c。差分数组无需单独构造： 差分有一个很省事的构造技巧——直接用”插入”操作完成初始化。
先假设原数组 a 中所有数全为 0，那么这个数组的差分数组也全为 0；
然后对 a 数组的每个元素做插入操作（把 a[i][j] 看成”对单点区间 (i,j,i,j) 加 a[i][j]”），最后还原数组即可得到更新后的数组。这样就不需要单独推导差分数组的构造公式，所有操作统一成”插入”这一种。
一维数组插入
二维数组插入
示例代码
1.实现一维差分对数组实现片段插入
import java.util.Scanner;public class Main { public static void main(String[] args) { Scanner sc= new Scanner(System.in); int n = sc.nextInt(); int[] a = new int[1000]; int[] b= new int[1000]; for (int i = 1; i <= n; i++) { a[i] = sc.nextInt(); } for (int i = 1; i <= n; i++) { insert(i,i,a[i],b); } insert(1,4,1,b); //求原来数组 for (int i = 1; i <= n; i++) { b[i] += b[i-1]; } for (int i =1; i <= n; i++) { System.out.println(b[i]); } } public static void insert(int i,int j ,int c,int[] a){ a[i] += c; a[j+1] -= c; }
}2.实现二维数组差分对数组实现范围插入
import java.util.Scanner;public class Main { public static void main(String[] args) { Scanner sc= new Scanner(System.in); int n = sc.nextInt(); int m = sc.nextInt(); int[][] a = new int[100][100]; int[][] b= new int[100][100]; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m ; j++) { a[i][j] = sc.nextInt(); } } for (int i = 1; i <= n; i++) { for (int j = 1; j <=m ; j++) { insert(i,j,i,j,a[i][j],b); } } insert(1,1,4,4,1,b); //求原来数组 for (int i = 1; i <= n; i++) { for (int j = 1; j <= m ; j++) { b[i][j] = b[i-1][j] + b[i][j-1] -b[i-1][j-1] + b[i][j]; } } for (int i =1; i <= n; i++) { System.out.println(); for (int j = 1; j <= m ; j++) { System.out.print(b[i][j] + " "); } } } public static void insert(int x1,int y1,int x2,int y2 ,int c,int[][] b){ b[x1][y1] += c; b[x2+1][y1] -=c; b[x1][y2+1] -=c; b[x2+1][y2+1] += c; }}如果这篇文章对你有帮助，欢迎分享给更多人！
部分信息可能已经过时