1. 从“暴力累加”到“差分”一个效率思维的转变如果你写过C的算法题尤其是那些涉及到频繁对数组某个区间进行增减操作的题目你大概率遇到过这种场景题目要求你对一个长度为n的数组执行m次操作每次操作给区间[l, r]内的所有元素都加上一个值c。最后问你操作完的数组是什么样。新手的第一反应往往是写一个双重循环外层遍历m次操作内层遍历[l, r]区间逐个元素加上c。这个思路非常直观我们称之为“暴力累加法”。它的时间复杂度是O(m * n)在n和m都达到10^5级别时这个算法会超时因为计算量可能高达10^10远超普通计算机一秒能处理的量级约10^8次运算。那么有没有一种方法能把区间修改的操作时间复杂度从O(n)降到O(1)从而让整体复杂度优化到O(m n)呢这就是差分算法要解决的核心问题。差分本质上是一种“预处理”和“懒更新”思想的数据结构它不直接操作原数组而是维护一个“变化量”数组。通过巧妙地记录变化的起点和终点把对一片区域的连续操作压缩成对两个端点的单点操作。等所有修改指令都下达完毕后再一次性“结算”出最终每个位置的真实值。这种“先记账后汇总”的思路在处理大规模、高频率的区间更新问题时效率提升是数量级的。理解差分不仅是掌握了一个算法模板更是学习了一种高效的编程思维模式。它和前缀和算法是一对“逆运算”常常在题目中成对出现。接下来我将从一维差分最朴素的原理开始带你彻底搞懂它为什么能工作然后给出万用模板和经典例题的剖析最后再扩展到更复杂的二维差分场景。你会发现一旦理解了核心思想所谓的“模板”不过是几行固定代码而已。2. 一维差分原理、构建与操作全解析2.1 差分数组的定义与构建逻辑假设我们有一个原始数组a长度为n通常下标从1开始方便处理边界。我们定义它的差分数组b满足这样一个关系原始数组a是差分数组b的前缀和数组。用公式表示就是a[i] b[1] b[2] ... b[i]或者等价地b[i] a[i] - a[i-1]当i 2时并且我们约定b[1] a[1]。这个定义是理解差分的关键。b[i]记录了a[i]相对于a[i-1]的变化量。如果a是平稳的b的值就很小如果a在某处发生突变b的对应位置就会有一个大的值。如何构建差分数组根据定义我们可以用O(n)的时间初始化差分数组bvectorint a(n1); // 假设a已填充数据a[0]未使用 vectorint b(n2, 0); // 通常将b声明为n2大小为后续操作留出r1的空间 // 构建差分数组 for (int i 1; i n; i) { b[i] a[i] - a[i-1]; }这里有一个更巧妙且常见的初始化方法尤其当我们从全零数组开始通过一系列操作来得到目标数组时我们可以认为初始的a数组和b数组都是全零。那么将a[i]设置为某个值c这个操作等价于在区间[i, i]上执行一次加c的操作。根据我们即将介绍的区间修改方法这可以通过b[i] c; b[i1] - c;来实现。这种“化初始化为操作”的思想在解题时非常有用。2.2 区间修改的魔法O(1)复杂度的实现现在来到差分最核心的部分如何用O(1)的时间实现对原数组a的区间[l, r]所有元素加c。答案是只需要对差分数组b做两个单点修改b[l] c; b[r1] - c;为什么这样是有效的让我们回到定义a[i]是b[1..i]的和。当我们执行b[l] c后对于所有i l的位置它们在计算前缀和时都会多加上这个c。也就是说从a[l]开始往后的所有元素都隐式地增加了c。但这并不是我们想要的我们只希望[l, r]区间内的元素增加c。所以我们需要在r1这个位置“刹车”执行b[r1] - c。这样对于所有i r1的位置它们在计算前缀和时先加上了c因为b[l]增加了又减去了c因为b[r1]减少了净变化为零。而对于i在[l, r]区间内的情况它们只受到了b[l] c的影响因此前缀和增加了c。这个过程就像是在一条河流的l处倒入一桶染料染料会一直流到下游。为了不让染料流到r之后的地方我们在r1处设置一个净化装置把染料清除掉。最终只有[l, r]这段河道被染色。2.3 从差分数组反推原数组前缀和还原在所有区间修改操作都记录在差分数组b之后我们如何得到修改后的原数组a‘呢根据定义对差分数组b求前缀和得到的就是更新后的原数组。vectorint a_new(n1, 0); for (int i 1; i n; i) { a_new[i] a_new[i-1] b[i]; } // 此时 a_new[i] 就是经过所有操作后原位置 i 的值如果题目不要求保留原始数组a我们通常可以直接用b的前缀和覆盖掉a或者用一个变量累加前缀和并输出。2.4 一维差分通用模板与注释结合以上步骤我们可以整理出一个清晰、健壮的一维差分模板。这个模板假设数组下标从1开始这是算法竞赛中的常见做法能有效避免下标减1的边界错误。#include iostream #include vector using namespace std; int main() { int n, m; // n: 数组长度 m: 操作次数 cin n m; vectorint a(n 2, 0); // 原数组多开一些空间防止越界 vectorint b(n 2, 0); // 差分数组通常比原数组多开1因为操作可能用到r1 // 1. 读取初始数组并构建差分数组 for (int i 1; i n; i) { cin a[i]; // 构建差分数组b[i] a[i] - a[i-1]; // 这里采用直接赋值法等同于 b[i] a[i]; b[i1] - a[i]; b[i] a[i]; b[i 1] - a[i]; } // 2. 执行m次区间加操作 while (m--) { int l, r, c; cin l r c; // 核心操作O(1)复杂度完成区间[l, r]加c b[l] c; b[r 1] - c; } // 3. 通过差分数组前缀和还原操作后的数组 for (int i 1; i n; i) { // 计算当前前缀和即更新后的a[i] b[i] b[i - 1]; // 将b自身直接变为前缀和数组即更新后的a cout b[i] ; } return 0; }注意模板中第三步我们直接在b上计算前缀和并输出这实际上破坏了b作为差分数组的结构。如果后续还需要进行更多轮操作则需要备份原始差分数组或者使用另一个数组来存储前缀和。这是空间优化和代码简洁性之间的一个权衡在一次性求解的问题中很常用。3. 一维差分实战经典例题剖析与避坑指南理解了原理和模板我们通过两道经典例题来巩固并分享一些实操中的心得和易错点。3.1 例题一基础区间修改AcWing 797. 差分题目描述 输入一个长度为n的整数序列。接下来输入m个操作每个操作包含三个整数l, r, c表示将序列中[l, r]之间的每个数加上c。请你输出进行完所有操作后的序列。输入格式 第一行包含两个整数n和m。 第二行包含n个整数表示整数序列。 接下来m行每行包含三个整数l, r, c。输出格式 共一行包含n个整数表示最终序列。思路分析 这是差分算法最直接的应用。我们不需要关心初始数组是怎么来的只需要知道差分数组b初始时如何对应这个初始数组。可以采用2.1节提到的“化初始化为操作”的思想假设原数组a和差分数组b初始全为0。那么读入初始数组a[i]的过程可以看作是进行了n次区间[i, i]加a[i]的操作。这样我们就可以用同一套b[l] c; b[r1] - c;的代码来处理初始化和后续修改逻辑非常统一。参考代码#include iostream using namespace std; const int N 100010; int b[N]; // 只使用差分数组 int main() { int n, m; scanf(%d%d, n, m); // 读取初始序列并视为在[i,i]区间加a[i] for (int i 1; i n; i) { int x; scanf(%d, x); b[i] x; b[i 1] - x; } // 处理m次操作 while (m--) { int l, r, c; scanf(%d%d%d, l, r, c); b[l] c; b[r 1] - c; } // 输出结果 for (int i 1; i n; i) { b[i] b[i - 1]; // b[i]现在存储的是前缀和即最终答案 printf(%d , b[i]); } return 0; }3.2 例题二差分结合前缀和求最终影响洛谷P2367 语文成绩题目描述 老师有n个学生给出初始成绩。进行m次加分操作每次给[l, r]区间内的学生成绩加c。但老师很粗心可能有的学生被重复加分。求所有操作结束后成绩最低是多少分输入输出略。思路分析 这道题在基础区间修改之上增加了一个“求最小值”的要求。步骤依然是用差分记录所有修改操作。通过前缀和还原出每个学生最终被加了多少分注意这不是最终成绩而是增加的量。将每个学生的初始成绩加上其对应的增加量得到最终成绩并在过程中维护最小值。关键点与避坑数组大小因为操作中会用到b[r1]所以差分数组b的大小至少要是n2否则当r n时b[r1]会越界。这是一个非常常见的运行时错误。多次操作的影响叠加差分的美妙之处在于无论进行多少次区间加操作这些操作的影响都通过b数组线性叠加。最后求一次前缀和就得到了每个位置的总变化量。不存在操作顺序问题因为加法满足交换律和结合律。还原时的遍历顺序计算前缀和时必须从i1开始顺序遍历。因为b[i]的新值依赖于b[i-1]的旧值。如果写成for (int i1; in; i) b[i] b[i-1];是正确的。如果试图用并行或倒序的方式就会出错。实操心得 在调试差分相关的代码时如果结果不对我建议用一个极小的例子手动模拟。例如n3初始数组为[1,2,3]执行一次操作[1,2] 5。手动写出a,b的每一步变化。这个方法能帮你快速定位是构建、修改还是还原的环节出了逻辑问题。另外务必注意数据范围和类型如果c可能很大累加后可能超出int范围就需要使用long long。4. 升维思考二维差分原理与可视化理解当问题从一维数组扩展到二维矩阵比如图像处理、子矩阵区域修改时二维差分就派上了用场。其核心思想与一维一脉相承但操作从两个点变成了四个点。4.1 二维差分数组的定义假设我们有一个二维原始矩阵a[][]大小为n x m。我们定义其对应的二维差分矩阵b[][]满足以下关系原始矩阵a[i][j]是差分矩阵b中从(1,1)到(i,j)这个子矩阵的所有元素之和。换句话说a是b的二维前缀和。反过来b[i][j]可以通过二维前缀和的逆运算求得但更常用的方法是利用其“影响”来定义。4.2 子矩阵区域修改的O(1)操作我们希望用O(1)的时间对原矩阵a中左上角为(x1, y1)右下角为(x2, y2)的矩形区域内的所有元素加上一个值c。对二维差分矩阵b的操作如下b[x1][y1] c; b[x1][y21] - c; b[x21][y1] - c; b[x21][y21] c;为什么是这四个点我们可以借助“影响扩散”的思想来理解这比死记硬背要牢固得多。想象b矩阵记录的是在某个点注入的“影响值”。b[x1][y1] c表示在(x1, y1)点注入一个c的影响。根据二维前缀和的定义这个c的影响会扩散到所有(ix1, jy1)的点即整个右下方向的无穷大区域。但这显然不是我们想要的矩形区域。我们需要把超出目标矩形[x1, x2] x [y1, y2]的影响给“抵消”掉。b[x1][y21] - c这个操作在矩形右边的外侧一列y21注入一个-c的影响。它的作用范围是(ix1, jy21)。这个-c和之前的c叠加使得对于所有j y21即矩形右边的区域在ix1的范围内净影响为0。这就把右边多余的影响消除了。b[x21][y1] - c同理这个操作在矩形下边的外侧一行x21注入一个-c的影响作用范围是(ix21, jy1)。它消除了下边多余的影响。然而经过上面两步区域(ix21, jy21)即矩形的右下角外部被多减了一次c因为它同时满足jy21和ix21。所以我们需要b[x21][y21] c来把这个多减的c加回来保证该区域净影响为0。这个过程类似于在一维差分中“加一头减一头”的二维扩展可以类比为在二维平面上打补丁。你可以画一个坐标系标出(x1,y1),(x1, y21),(x21, y1),(x21, y21)这四个点然后想象c和-c的影响范围就能直观看到它们如何精确地框出目标矩形。4.3 通过二维前缀和还原矩阵在所有子矩阵加操作完成后我们需要从差分矩阵b还原出操作后的原矩阵a‘。这需要通过计算二维前缀和来实现。二维前缀和公式为S[i][j] S[i-1][j] S[i][j-1] - S[i-1][j-1] b[i][j]其中S[i][j]就是我们要的a‘[i][j]。我们可以直接在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] 就是 a‘[i][j] } }5. 二维差分模板与综合应用例题5.1 二维差分通用模板下面是一个完整的二维差分模板包含了初始化假设从零开始构建、多次子矩阵加操作和最终结果输出。#include iostream using namespace std; const int N 1010; // 根据题目数据范围调整 int b[N][N]; // 二维差分数组 // 插入函数对以(x1,y1)为左上角(x2,y2)为右下角的子矩阵所有元素加c void insert(int x1, int y1, int x2, int y2, int c) { b[x1][y1] c; b[x1][y2 1] - c; b[x2 1][y1] - c; b[x2 1][y2 1] c; } int main() { int n, m, q; // n行m列q次操作 scanf(%d%d%d, n, m, q); // 1. 初始化读取原矩阵并视为对单个单元格(i,j)进行插入操作 for (int i 1; i n; i) { for (int j 1; j m; j) { int x; scanf(%d, x); insert(i, j, i, j, x); // 在(i,j)到(i,j)的“子矩阵”加x } } // 2. 进行q次子矩阵加操作 while (q--) { int x1, y1, x2, y2, c; scanf(%d%d%d%d%d, x1, y1, x2, y2, c); insert(x1, y1, x2, y2, c); } // 3. 计算二维前缀和得到结果矩阵 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]; printf(%d , b[i][j]); } puts(); // 换行 } return 0; }将核心操作封装成insert函数是一个好习惯它让主逻辑更清晰也减少了出错的可能。5.2 例题激光炸弹一种二维前缀和与差分的结合思路问题简述 地图上有N个目标每个目标有一个价值w_i位于坐标(x_i, y_i)。有一种炸弹能摧毁边长为R的正方形区域边平行于坐标轴内的所有目标。求一颗炸弹最多能摧毁多少价值。输入格式 第一行N和R接下来N行x_i, y_i, w_i思路分析 这不是一个直接的差分题但它的高效解法依赖于二维前缀和而差分是前缀和的逆运算理解其一必有助于理解另一个。我们可以将目标价值累加到地图矩阵a[x][y]上注意坐标可能从0开始需要统一平移至从1开始。然后对矩阵a计算二维前缀和s[][]使得s[i][j]表示原点到(i,j)的矩形内总价值。对于任意一个边长为R的正方形假设右下角为(i,j)左上角为(i-R1, j-R1)其内部总价值可以通过前缀和O(1)计算value s[i][j] - s[i-R][j] - s[i][j-R] s[i-R][j-R]。遍历所有可能的正方形位置取最大值。与差分的联系 在这个问题中我们是在“初始化”阶段将N个点值加到矩阵上。如果不用前缀和而是用差分该如何做我们可以把每个目标(x,y)的价值w看作是对一个1x1的子矩阵[x,x] x [y,y]加w。这样用二维差分的insert操作N次就能构建出初始的差分矩阵b。然后再对b求二维前缀和得到的就是我们需要的、包含所有目标价值的矩阵a。后续步骤完全一样。避坑指南坐标偏移题目坐标可能从0开始而我们的数组通常从1开始索引需要进行1的偏移否则在计算前缀和时会访问到s[0][j]或s[i][0]导致错误。边界处理炸弹的边长R可能大于地图范围需要取min(R, 最大坐标)。在计算正方形价值时要确保索引i-R和j-R不小于0或1取决于偏移。空间优化如果坐标范围很大比如5000直接开int a[5001][5001]可能会超过内存限制约 100MB。需要根据题目内存限制谨慎评估。有时需要将坐标离散化或者使用动态数组如vector。通过这道题我们可以看到前缀和与差分是处理静态区间矩形求和与区间修改问题的利器。它们的思想可以推广到更高维度虽然三维情况不常见但理解了一维和二维其扩展是自然而然的。掌握这两种工具能让你在面对一系列算法竞赛和面试中的数组/矩阵处理问题时拥有更高效、更清晰的解题思路。