在算法刷题LeetCode、蓝桥杯、ACM和工程开发中我们经常遇到「多次对数组的某个区间统一修改最后查询数组结果」的场景。如果用暴力遍历修改每次区间操作的时间复杂度是O(n)O(n)O(n)当修改次数极多时效率会非常低。而差分算法就是解决这类问题的终极利器它能让区间修改的时间复杂度降到O(1)O(1)O(1)最后仅用一次O(n)O(n)O(n)的前缀和计算就能得到最终数组。一、差分的核心定位差分算法的本质差分与前缀和是一对互逆运算对差分数组求前缀和 → 得到原数组对原数组求差分 → 得到差分数组。所有差分的操作都是围绕这个核心互逆关系展开的二、一维差分一维差分是所有差分的基础解决一维数组的区间修改 最终查询问题。2.1 核心思想假设我们有原数组a[]长度为nnn下标从 1 开始差分数组d[]与原数组等长定义公式{d[1]a[1]d[i]a[i]−a[i−1](i1) \begin{cases} d[1] a[1] \\ d[i] a[i] - a[i-1] \quad (i1) \end{cases}{d[1]a[1]d[i]a[i]−a[i−1](i1)​还原公式前缀和a[i]d[1]d[2]...d[i]a[i] d[1] d[2] ... d[i]a[i]d[1]d[2]...d[i]一句话总结差分数组记录原数组的相邻差值前缀和能把差值还原为原数组。2.2 核心操作O(1) 区间修改这是差分算法最核心、最实用的功能需求对原数组的区间 [l, r] 统一加上一个值 val。差分固定操作仅2步O(1)d[l] val从位置lll开始所有原数组元素都会加vald[r1] - val从位置r1r1r1开始抵消之前的加值保证只修改 [l, r]。原理因为原数组是差分数组的前缀和修改差分数组的两个点就能通过前缀和批量影响原数组的一个区间。2.3 算法步骤初始化原数组 a[] 和差分数组 d[]对所有区间修改需求用差分固定公式操作差分数组对差分数组求前缀和还原出最终的原数组。2.4 实战代码#includeiostream#includevectorusingnamespacestd;intmain(){// 1. 定义原数组下标从1开始规避边界问题vectorinta{0,1,2,3,4,5};// a[1]1, a[2]2...a[5]5intna.size()-1;// 有效长度5// 2. 初始化差分数组vectorintd(n2,0);// 多开2位防止r1越界for(inti1;in;i){d[i]a[i]-a[i-1];}// 3. 区间修改[2,4] 统一 2intl2,r4,val2;d[l]val;d[r1]-val;// 4. 前缀和还原原数组for(inti1;in;i){a[i]a[i-1]d[i];}// 输出结果1 4 5 6 5for(inti1;in;i){couta[i] ;}return0;}三、二维差分一维差分解决线段区间修改二维差分解决矩阵子区间修改比如给矩形区域的所有元素加val。3.1 核心思想和一维完全一致二维差分数组 d[][] → 二维前缀和 → 原数组 a[][]原数组 a[][] → 二维差分 → 差分数组 d[][]。3.2 核心操作O(1) 子矩阵修改需求给矩阵中左上角(x1,y1)(x1,y1)(x1,y1)、右下角(x2,y2)(x2,y2)(x2,y2)的子矩阵统一加 val。二维差分固定公式4步O(1)d[x1][y1] val;d[x1][y21] - val;d[x21][y1] - val;d[x21][y21] val;最后对二维差分数组求前缀和即可还原最终矩阵。3.3 实战代码#includeiostream#includevectorusingnamespacestd;intmain(){// 3x3 矩阵下标从1开始vectorvectorinta{{0,0,0},{0,1,2},{0,3,4}};intn2,m2;// 初始化二维差分数组vectorvectorintd(n2,vectorint(m2,0));for(inti1;in;i){for(intj1;jm;j){d[i][j]a[i][j]-a[i-1][j]-a[i][j-1]a[i-1][j-1];}}// 子矩阵修改(1,1)~(2,2) 统一 5intx11,y11,x22,y22,val5;d[x1][y1]val;d[x1][y21]-val;d[x21][y1]-val;d[x21][y21]val;// 二维前缀和还原for(inti1;in;i){for(intj1;jm;j){a[i][j]a[i-1][j]a[i][j-1]-a[i-1][j-1]d[i][j];}}// 输出结果6 7 / 8 9for(inti1;in;i){for(intj1;jm;j){couta[i][j] ;}coutendl;}return0;}四、差分算法核心重点这是新手最容易忽略、最容易出错的点牢记以下5点1. 核心底层逻辑差分 ↔ 前缀和 互逆所有操作的根源没有这个关系差分就不成立。2. 时间复杂度碾压暴力法暴力区间修改O(n)O(n)O(n)每次差分区间修改O(1)O(1)O(1)每次最终还原O(n)O(n)O(n)一维/O(nm)O(nm)O(nm)二维。修改次数越多差分优势越明显3. 下标必须从 1 开始这是差分的最佳实践避免 i-1 出现负数避免 r1 越界差分数组多开2位空间。4. 固定公式死记理解一维区间修改d[l]val、d[r1]-val二维子矩阵修改4行固定代码。5. 必须做前缀和还原差分只是记录修改最后一定要通过前缀和才能得到最终数组五、适用场景一维数组多次区间增减最后查询数组二维矩阵多次子矩阵增减最后查询矩阵算法题区间覆盖、区间增量、差分数组优化等题型。六、总结差分算法是区间修改问题的最优解核心只有一句话用差分数组记录区间修改O(1)用前缀和还原最终结果O(n)。一维差分掌握2行修改公式二维差分掌握4行修改公式核心差分与前缀和的互逆关系。吃透这个思想所有区间修改类问题都能轻松秒杀