1. 区间加法的暴力困境差分到底解决了什么问题1.1 一道看着不需要任何技巧的题前段时间有个同学拿着一道题来问数组长度一千万接下来一千万次操作每次给一个区间[l, r]里的所有数加上同一个值v最后把整个数组输出。他写了个双重循环本地跑小数据完全正确提交上去直接超时把cin换成scanf、把vector换成数组、加了一堆读入优化结果还是超时。问题不在常数上。他这个写法的复杂度是O(nm)一千万乘一千万就是 10^14 这个量级你把每条指令优化到 1 纳秒都跑不完。这种题的出现本身就是个信号出题人压根没打算让你去模拟这件事他想看的是你有没有意识到——区间整体加一个数这个动作在某种表示下可以只花 O(1) 的时间。这个某种表示就是差分。差分Difference Array这个东西名字听着挺唬人原理其实朴素得有点过分它不存原数组而是存相邻两个数的差。你把它想成记账就很好理解了——原数组记的是每天账上有多少钱差分数组记的是今天比昨天多了多少钱。前者想算某天的余额得从头加后者想算某天的余额也是从头加但后者想表达从第 3 天到第 8 天每天都多发 100 块这件事只需要在账本上改两笔第 3 天记一笔 100第 9 天记一笔 -100。中间那几天完全不用动。适合看这篇的人大概分三类正在准备算法笔试面试、被区间操作题反复折磨的写过一些题但一直靠线段树硬顶、想搞明白什么时候不用上线段树的以及已经会写差分模板、但二维或者树上差分每次都要照着抄、抄完还得debug半天的。不管属于哪一类下面的推演都是从头讲起的不预设你背过模板。1.2 前缀和与差分是一对互逆的操作要理解差分绕不开前缀和这两个东西是同一枚硬币的两面。前缀和是从前往后累加差分是相邻作差学过一点微积分的人可以立刻反应过来这就是离散版本的积分与求导。具体说给定原数组a[1..n]前缀和S[i] S[i-1] a[i]从a得到S差分d[i] a[i] - a[i-1]从a得到d关键在于这两个操作互为逆运算。你对a求一次差分得到d再对d求一次前缀和一定回到a。这个性质不是巧合是裂项相消的必然结果下一节会把它拆开揉碎讲。正因为互为逆运算所以前缀和擅长的题型和差分擅长的题型正好是互补的操作类型前缀和差分单点修改 区间查询不适合改一个点要重建不适合区间修改 单点查询不适合极其适合O(1) 改区间修改 全局最终查询不适合最适合O(nm)静态数组的区间求和最适合O(1) 查询不适合记住这张表比背十道题的解法都管用。看到给一段区间同时加上/减去某个量脑子里第一反应就该是差分看到求一段区间的和数组不变第一反应就该是前缀和。1.3 什么信号出现时就该把差分拿出来不是所有区间题都能用差分。有几个特征非常明确只要命中其中一条基本可以确定出题人想考差分整批修改、最后统一询问。这是差分最纯正的用法。所有修改做完之后只问一次结果那么每次修改的 O(1) 和最后还原的 O(n) 加起来就是全部开销中间没有任何查询穿插完美。题目关心的是叠加次数而不是叠加结果。比如数轴上有一堆线段问哪个点被覆盖次数最多你完全不需要知道每个点具体被哪几条线覆盖只需要知道次数。给每条线段的左端点 1、右端点后一位 -1最后跑一遍前缀和最大值就出来了。这类题用线段树当然也能做但纯属浪费。操作是增量形式给出的。比如第 i 天比第 i-1 天价格上涨了 x或者从第 l 个人到第 r 个人每人多发 v 元奖金。数据本身就长成差分的模样硬转成绝对值反而是给自己找麻烦。反过来有两种情况要慎用甚至不能用一是修改和查询交替出现也就是每次改完立刻要问当前某个位置的值这时候单靠差分不行得配树状数组或者直接上线段树二是区间操作不是简单的加减比如区间取 max、区间赋值、区间乘这些不满足可减性差分就失效了得老老实实上数据结构。2. 差分数组的定义与还原那条d[i] a[i] - a[i-1]到底在干嘛2.1 定义摆出来先手算一遍定义很简单一维差分数组d满足d[1] a[1] d[i] a[i] - a[i-1] (i 2)拿一个六元素的数组走一遍比看十行公式管用下标 i123456原数组 a377291差分 d340-57-8看第二行到第三行的变化3是自己7-347-702-7-59-271-9-8。有没有发现什么差分数组里的零对应的是原数组这里没有变化。上表中d[3]0正好说明a[3]和a[2]一样。这是个很实用的直觉差分数组非零的位置越少原数组越平滑。这个直觉反过来用就是差分的核心价值所在——如果你想让原数组在某一段上产生一个恒定的变化那么在差分数组里你只需要在段的两端制造两个非零点中间的差分值全都是零也就是说根本不用写。这就是为什么区间修改能从 O(长度) 降到 O(1)。2.2 用裂项相消解释前缀和能还原原数组很多人背下了差分数组求前缀和就是原数组但没想过为什么。把式子写开就一目了然了。对d求前缀和得到第i项d[1] d[2] d[3] ... d[i] a[1] (a[2]-a[1]) (a[3]-a[2]) ... (a[i]-a[i-1])除了第一项的a[1]和最后一项的a[i]中间所有项都是加一个减一个成对抵消的。a[2]加了又减了a[3]加了又减了一路消下去最后只剩下a[i]。这个现象叫裂项相消它解释了为什么求一次差分再求一次前缀和能原样返回。理解了这一层后面所有变体就都能自己推了。二维差分为什么是四个角加减因为二维前缀和的裂项相消是沿着行和列两个方向同时进行的。树上差分为什么是diff[u] v, diff[v] v, diff[lca] - v, diff[fa[lca]] - v因为树上的前缀和是从根往下的路径求和沿着路径抵消之后就落在那个形式上。所有这些都不是需要死记的东西推一遍裂项就出来了。2.3 三条必须记牢的性质第一差分是线性的。如果a的差分是d1b的差分是d2那么ab的差分就是d1d2。这条性质意味着你可以把多个修改的差分效果直接叠加不用管先后顺序也不用担心互相干扰。实践中经常出现我先处理第一类操作再处理第二类操作的写法靠的就是这个。第二差分数组的和等于原数组最后一项。把d全部加起来按裂项相消中间全部消掉只剩a[n]。这条可以用来检查代码有没有写错如果你算出来的差分总和跟原数组末尾对不上中间某个地方肯定出问题了。第三还原的顺序是不可交换的。一维差分还原时必须从左往右滚动前缀和二维差分还原时必须先上后下、先左后右用已经还原好的上方和左侧去更新当前格。顺序搞反了结果会错得非常隐蔽——小数据可能碰巧对大数据全错。3. 区间修改只动两个端点推演、验证与代码落地3.1 从改一段到改两个点的思维跳跃现在要把[l, r]这一段全部加v。如果直接改原数组那就要动r-l1个数。但如果改的是差分数组呢我们希望的最终效果是a[l]到a[r]都比原来多v其余不变。对应的差分变化是d[l] a[l] - a[l-1]a[l]多了va[l-1]没变所以d[l]多了v对于l i ra[i]和a[i-1]都多了v差值不变所以d[i]不变d[r1] a[r1] - a[r]a[r1]没变而a[r]多了v所以d[r1]少了v再往后的项前后都没变差值不变结论就是两句话d[l] v d[r1] - v看到这里你应该有点感觉了这就是 1.1 节里说的第 3 天记 100第 9 天记 -100。差分只关心变化发生的那一刻不关心变化持续多久。中间那段持续的时间在还原的时候会被前缀和自动补上。3.2 拿具体数字完整追踪一遍空口说没感觉直接跑一组数据。原数组全是 0长度 8做三次操作[2,5] 3、[1,3] 2、[6,8] 4。第一步[2,5] 3d[2] 3d[6] - 3。第二步[1,3] 2d[1] 2d[4] - 2。第三步[6,8] 4d[6] 4d[9] - 4注意 819 已经越界实际实现时数组要开到n2。此时差分数组下标123456789(越界)d230-20100-4对d做前缀和得到最终数组下标12345678累加过程223505-230314040结果25533444人工核对位置 1 只被第二条覆盖得 2位置 2、3 被第一和第二条覆盖得 325位置 4、5 只被第一条覆盖得 3位置 6、7、8 只被第三条覆盖得 4。完全一致。顺带说一句这组数据其实就是数轴上若干线段问每个点被覆盖的权值和的原型。很多统计类的题本质就是这么个东西只是包了一层业务外衣。3.3 代码落地与下标体系的选择伪代码看一眼就够了真正容易出错的是下标体系。有两种主流写法各有各的坑。写法一1-indexed差分数组长度开到 n2// a[1..n] 为原数组d[1..n1] 为差分数组 vectorlong long d(n 2, 0); for (int i 1; i n; i) d[i] a[i] - a[i - 1]; // 区间 [l, r] 加 v d[l] v; d[r 1] - v; // 还原 for (int i 1; i n; i) { d[i] d[i - 1]; a[i] d[i]; // 还原后 d[i] 就是 a[i] }写法二0-indexed差分数组长度开到 n1vectorlong long d(n 1, 0); // d[n] 存的是越界哨兵 for (int i 0; i n; i) d[i] a[i] - (i ? a[i - 1] : 0); d[l] v; d[r 1] - v; // r n-1 时写到 d[n]合法 for (int i 0; i n; i) { if (i) d[i] d[i - 1]; a[i] d[i]; }两种写法都对但绝对不能在同一个文件里混用。混用的后果是d[r1]在 0-indexed 下写到了d[n]而更新循环只跑到n-1那个减掉的-v永远生效不了或者反过来在 1-indexed 下忘了给d开出n1这一格r n时数组越界本地小数据不崩评测机上直接给你段错误。一个便宜的自检办法写完d[r1] - v之后顺手 print 一下n1或者n这个位置的值看它是不是在数组容量之内。这行检查能省掉大量重测。3.4 修改和查询交叉出现时怎么办前面一直强调所有修改做完再统一还原那如果有人非要边改边问呢两种处理思路。第一种如果查询也是区间形式的且只需要最终结果那就把修改全部收集起来最后一次性还原再回答所有查询。离线处理O(nmq)。第二种如果必须在线差分数组本身是不够的因为它只记录了变化点你查任意位置都得从头前缀和一遍。这时候要么直接上树状数组单点改、区间查正好是差分的天然搭档——把差分数组交给树状数组维护区间修改变成两次单点改区间查询变成两次前缀和查询要么上线段树。个人经验是只要题目里出现了每次操作后立刻输出就别纠结了树状数组或线段树二选一省时间。4. 二维差分容斥在矩阵上的四次落笔4.1 二维差分的定义长什么样一维是相邻作差二维就是行方向作差再列方向作差最终形式是一个二维前缀和的逆运算d[i][j] a[i][j] - a[i-1][j] - a[i][j-1] a[i-1][j-1]这个式子第一次看到会觉得莫名其妙为什么加加减减这么多项把它和一维对比就通了。一维里d[i] a[i] - a[i-1]是当前减左边一个二维里当前格子的左邻有两个上方和左方共同邻居有一个左上用容斥原理一算就是减两次加一次。这个 左上角的项不是凭空补的而是为了把被重复减掉的部分还回去。还原的时候反过来用二维前缀和d[i][j] d[i-1][j] d[i][j-1] - d[i-1][j-1]还原完之后d[i][j]就是a[i][j]。4.2 子矩阵加法为什么是四个角现在要给左上角(x1, y1)、右下角(x2, y2)的整个子矩阵加v。核心思路和一维完全一样只在变化开始和变化结束的位置记账。二维的麻烦在于变化会在两个方向上同时结束所以要记四笔。推法很直接先假设d里只有一笔d[x1][y1] v。还原时二维前缀和会把这一笔扩散到所有i x1 j y1的格子也就是右下角的整个无限区域。但我们要的只是到x2, y2为止的那一块多出来的部分得削掉削掉右边多出来的在(x1, y21)处-v把右边整片抹掉削掉下边多出来的在(x21, y1)处-v把下边整片抹掉右下角那一块被上面两笔各削了一次多削了一次所以在(x21, y21)处v补回来写成代码// 1-indexedd 数组尺寸 (n2) x (m2) void add(int x1, int y1, int x2, int y2, long long v) { d[x1][y1] v; d[x1][y2 1] - v; d[x2 1][y1] - v; d[x2 1][y2 1] v; }这四个符号 - - 是有规律的从左上到右下符号按奇偶性翻转行列各翻一次。记不住的时候就想被减了两次的地方要补回来符号自然就出来了。4.3 一个 3×3 的完整验算矩阵初始全 0给子矩阵(2,2)到(3,3)加 5。按公式写入列1列2列3列4行10000行2050-5行30000行40-505跑二维前缀和还原(2,2)5(2,3)d[2][3] d[1][3] d[2][2] - d[1][2] 0 0 5 - 0 5(2,4)-5 0 5 - 0 0(3,2)0 5 0 - 0 5(3,3)0 5 5 - 5 5(4,2)-5 0 5 - 0 0最终结果只有(2,2)(2,3)(3,2)(3,3)四个格子是 5其余全 0。正是要的效果。4.4 二维差分最容易写错的四个地方符号顺序写反。四个角的符号必须是左上 、右上 -、左下 -、右下 。写成 - -或者别的组合用单个修改测试的时候可能碰巧通过因为只有一个角起作用一叠加就全乱。越界没留余量。x21和y21最大能到n1和m1所以d必须开成(n2) * (m2)。这个在 C 里是硬伤vectorvectorlong long d(n2, vectorlong long(m2, 0))一行搞定别省。还原顺序写错。必须外层从上到下、内层从左到右并且用已经还原过的d[i-1][j]和d[i][j-1]。如果写成先算完整个数组再一次更新公式就退化成用原始差分值去算结果必错。溢出不检查。子矩阵面积大的时候一个格子的值可能是v * 面积。如果v是 1e9、面积是 1e10 量级int早就炸了。二维差分题里long long几乎是标配别赌。5. 差分的高阶变体树上差分、离散化与二阶差分5.1 树上差分点差分和边差分差在哪树上的情况稍微绕一点。一维数组是一条链树有很多分支但本质没变——你依然是在给一条路径整体加值只不过这条路径现在是树上两个节点之间的路径。定义diff[u]为节点u上的差分值做完所有修改后对每个节点统计其子树的 diff 和得到的值就是该节点最终的值。这个子树求和就是树上的前缀和。给u到v的路径上所有点加w写法是int g lca(u, v); diff[u] w; diff[v] w; diff[g] - w; diff[fa[g]] - w; // 如果 g 是根fa[g] 用 0 号虚拟节点承接为什么是这四项沿着u往上到根和v往上到根各加一次重合的部分是g到根这一段被加了两次所以要减掉一次diff[g] - wg本身在两条路径的终点都算过实际只需要一次所以要再减一次diff[fa[g]] - w。这个推导用容斥讲是最清楚的比死记强。给路径上所有边加w写法变成int g lca(u, v); diff[u] w; diff[v] w; diff[g] - 2 * w;区别在于边差分的归属是给边挂到深度更大的那个端点上此时lca对应的那条父边不属于这条路径所以一次性减掉两次而不是分两处减。提醒一句点差分和边差分的区别只在这最后一项写树剖或者倍增求 LCA 的模板的时候一定在代码注释里标清楚这是点差分还是边差分。我见过不止一次把点差分的模板拿去写边差分样例过了大数据挂得一塌糊涂。求lca的方式按数据规模选。点数10^5级别用倍增就够10^6级别并且多次查询的话可以上树剖或者 Tarjan 离线看个人顺手程度。5.2 离散化差分坐标范围到了 1e9 怎么办差分的一大前提是数组能开出来。如果题目给的坐标范围是[1, 10^9]你不可能开一个十亿的数组。这时候的做法是只关心端点把端点离散化。以数轴上有 n 条线段问被覆盖最多的点被几条线段覆盖为例vectorlong long xs; // 收集所有端点 for (auto seg : lines) { xs.push_back(seg.l); xs.push_back(seg.r 1); // 关键右端点后面一格也要收进来 } sort(xs.begin(), xs.end()); xs.erase(unique(xs.begin(), xs.end()), xs.end()); vectorint diff(xs.size() 2, 0); for (auto seg : lines) { int L lower_bound(xs.begin(), xs.end(), seg.l) - xs.begin(); int R lower_bound(xs.begin(), xs.end(), seg.r 1) - xs.begin(); diff[L] 1; diff[R] - 1; } int cur 0, best 0; for (size_t i 0; i xs.size(); i) { cur diff[i]; best max(best, cur); }这里最容易踩的坑是忘了把r1也收进离散化集合。如果你只收l和r那么某条线段的右端点和另一条线段的左端点相同时两个事件会被压缩到同一个下标上加减直接抵消覆盖数就少算了一段。加上r1之后线段右端点之后这个位置才有独立的坐标事件不会互相吞掉。另外离散化之后数组下标的分段含义变了每一段代表的是从xs[i]到xs[i1]-1这个区间判断最大值时不再需要区分具体点位直接取前缀和的最大值即可。但如果题目问的是最长被覆盖长度为多少这种带权的问题就需要用xs[i1] - xs[i]作为权重乘上去这时候前缀和的最大值不再等于答案得改成扫描线求最大连续段。5.3 区间加等差数列把差分再差一次还有一类题更刁钻给[l, r]加上一个等差数列第一项是a公差是d也就是a[i] a (i-l)*d。这时候一阶差分就不够用了因为一阶差分在区间内部不是常数而是一个固定值d在不断变化——换句话说一阶差分的差分二阶差分在区间内是常数。二阶差分D2[i] D[i] - D[i-1]其中D是一阶差分。对[l, r]加等差数列只需在二阶差分上改四笔D2[l] a; D2[l 1] d - a; D2[r 1] - a (long long)(r - l 1) * d; D2[r 2] a (long long)(r - l) * d;还原要跑两遍前缀和先把D2还原成D1再把D1还原成原数组。for (int i 1; i n; i) D1[i] D1[i - 1] D2[i]; for (int i 1; i n; i) a[i] a[i - 1] D1[i];拿l1, r3, a1, d1也就是加1,2,3验算一遍D2[1] 1D2[2] 0D2[4] - 1 3 4D2[5] 1 2 3。还原D11, 1, 1, -3, 0再还原a1, 2, 3, 0, 0。正确。这个技巧之所以值得单独拎出来是因为很多看起来必须上线段树的题用二阶差分能写到十几行而线段树要维护懒标记、要处理各种边界代码量差一个数量级。5.4 差分还能和别的技巧组合差分的本质是把区间操作转化为端点操作这个思路可以嫁接到很多地方。差分 二分答案。典型场景是最大化最小值类问题二分答案x然后判断是否存在一种方案使得所有段都满足某个条件。判断过程里往往需要统计每个位置被多少条满足条件的区间覆盖差分正好用来做这个统计。整体复杂度从O(n log n)的那部分降下来。差分 扫描线。求矩形并面积、矩形覆盖周长这类问题本质是沿一条轴扫描另一条轴上维护当前被覆盖的段数。事件点的加减就是差分的雏形只不过配了一棵线段树来维护区间覆盖次数。差分 哈希。想快速判断两个子串是否逐位差值相同这类问题时可以先对原串做差分再对差分串做哈希比较就变成了判等省掉一堆逐位比较。换个领域看差分思想到处都是。图像处理里的边缘检测本质是对像素做差分把平滑区域消掉只留下变化剧烈的地方时间序列分析里做差分来消除趋势项让序列变平稳增量式统计比如每天的新增用户数本身就是差分。这些场景和算法竞赛里的差分数组是同一个东西的不同外衣理解了本质迁移起来毫无障碍。6. 差分写错时的排查链路我踩过的那些坑6.1 下标体系混用是头号杀手前面提过一次但值得再强调。差分题的 bug 有相当一部分来自1-indexed 的定义、0-indexed 的循环这种混搭。具体表现是小数据都对大数据全错——因为越界写到了别的变量或者数组外的内存小数据时那块内存碰巧是 0结尾几个位置的值不对——因为d[r1]的-v写到了更新循环覆盖不到的位置结果整体偏移一位——d的初始化循环和还原循环起止点不一致排查办法很土但很有效拿n 5的小数组每个位置初始值设成不同的数比如1, 2, 3, 4, 5只做一次区间修改然后把d数组整个打印出来人工核对每个位置是否和手算一致。一次修改能过的代码多次修改基本也能过一次修改就错的代码别急着测大数据。6.2 溢出和负数差分的值可以是负数这很正常a[i]比a[i-1]小的时候差分就是负的。但如果你用无符号类型存差分数组负数会变成一个巨大的正数然后在前缀和的时候把整个数组带崩。差分数组一律用有符号类型这条没有例外。溢出的另一个来源是中间结果。假设每个位置加10^9做10^5次修改最终单点的值可能到10^14int直接爆。养成习惯只要是差分题long long起步二维差分更是必须。有人会说题目保证了答案在 int 范围内但差分数组的中间状态未必在——差分的每一项本身可能很大只是前缀和之后才回到范围内的。6.3 多组数据忘记清空多组测试数据是最容易翻车的地方。一维差分还好vector重新分配就干净了二维差分如果用了全局数组memset漏掉一行就是灾难。更隐蔽的是树上差分diff数组、邻接表、fa数组、depth数组任何一个没清干净第二组数据就开始跑飞。一个省事的做法是把所有需要清空的东西写成一个reset()函数main里每组数据开头调一次。别指望我记得清人一定会忘。6.4 树上差分的回溯顺序树上差分的还原是把子树的diff和往上累加这个过程必须在后序遍历里完成也就是先递归所有儿子把儿子的子树和加到自己身上再返回。如果写成前序父节点还没拿到儿子的值就先把自己传下去了结果全错。void dfs(int u, int p) { for (int v : g[u]) { if (v p) continue; dfs(v, u); diff[u] diff[v]; // 必须在递归之后 } }另外如果 LCA 用倍增实现fa[g]在g是根节点的时候是 0而 0 号虚拟节点的diff不需要参与统计所以最后统计答案时从 1 号节点开始遍历即可。这个细节不处理好根节点的值会莫名多出一截。7. 一个常被混淆的概念差分数组和差分约束系统最后必须澄清一件事因为搜索差分的时候这两样东西经常一起出现很多人被绕晕。差分数组是本文讲的这个是一种数据组织方式用来把区间操作转成端点操作复杂度优化。它属于技巧层面的东西代码量小没有图论。差分约束系统是另一回事它指的是一组形如x_j - x_i c的不等式求解是否存在一组解满足全部约束。标准做法是把每个不等式变成一条从i到j、权值为c的有向边然后跑最短路或者最长路判负环。它属于图论建模层面核心是三角形不等式和松弛。两者唯一的共同点是名字里都有差分两个字——因为差分约束里的约束条件本身就是两个变量的差。除此之外没有任何关系解法、复杂度、适用场景完全不同。搜索引擎把它们混在一起导致不少人学差分数组的时候误入差分约束的教程看了半天 SPFA 一脸懵。记住这条界限能省下不少时间。如果哪天你遇到一道题输入是一堆某两个量之差不超过某个值的约束要求判断可行性或者求极值那就该往差分约束那条路走了跟本文讲的区间加法完全不是一个路子。判断标准很清晰看题目问的是数组怎么变还是变量取什么值前者是差分数组后者是差分约束。从我自己做题和讲课的经验看差分这个技巧的难点从来不在代码在于看到题目的第一眼能不能反应过来这段操作可以只记两端。这个反应速度是靠数量堆出来的把一维、二维、树上、二阶这四种形态各写两三道一周之内就能形成条件反射。写完之后的验算也很关键我最常用的一招是拿最小规模的数据比如n3、m1手算一遍然后跟程序输出逐位对比。看起来笨但比盯着代码找符号错误快得多。
