差分数组入门：从“最高的牛”理解区间修改的O(1)技巧

先想清楚一个问题这道题为什么叫“最高的牛差分”我刚接触的时候也愣了一下差分我知道是前缀和的逆运算一个处理区间修改的常用技巧。但“最高的牛”是什么鬼刷了几道题才明白这道题是差分数组最经典的入门应用之一题目本身不难却把差分的精髓——把区间操作变成O(1)的两次单点修改——展现得淋漓尽致。今天这篇文章就好好拆一拆这道题顺便把差分数组从原理到应用彻底讲透新手能跟着复现老手也能看看有没有漏掉的细节。先说一下这道题的场景有N头牛站成一排已知最高的那头牛的高度是H又给了M对关系每对关系里的两头牛能互相看见也就是说这两头牛之间的所有牛的高度都必须严格小于这两头牛。题目要求每头牛可能的最大高度。是不是有点绕我当时第一次读也读了半天。本质上就是有一排未知高度的牛你只知道最高点的高度还知道一些“区间内不许有高于或等于两端”的约束要反推出每个位置可以取到的最大值。这类题用差分数组做就是标准解法而且代码短到离谱。这题适合谁看准备算法竞赛的、刷面试题手痒的、想搞懂差分数组到底怎么用的人都适合。就算你完全没接触过差分数组这篇文章也会从零开始把原理和代码一起讲透。1. 题目分析与暴力思路的困境1.1 读懂题目里的“互相看见”先别急着上代码把题目条件掰开揉碎。N头牛站一排我们不知道每头牛具体多高只知道最高的那头牛高度是H而且题目会明确告诉你最高牛在第几号位置。然后给了M条关系每条关系形如“a和b能互相看见”。能互相看见是什么意思不是眼神好而是地理上的a和b之间没有比它们更高的牛挡住视线。因为如果中间任何一头牛高度大于等于a或b中的较小者那至少有一方会被挡住就看不到了。严格一点说给定关系(a, b)后区间(a, b)内每一头牛的高度都必须严格小于这两头牛的高度。换句话说区间内的牛只能比两端矮不能跟两端一样高更不能更高。这里有个关键点关系是“双向约束”不是单方向的。a和b能互相看见意味着a的视线不被挡住b的视线也不被挡住所以区间内所有牛的高度都受到限制。这直接决定了解题方向——每出现一对关系就相当于说“区间内部的人高度不能超过某个上限”。很多人第一反应是那我直接用一个数组存高度初始全部为H每出现一对关系就把区间内部的牛全部减1最后输出不就完了吗思路是对的但问题是——这个“区间内部全部减1”操作如果每次都老老实实遍历区间内的每一个位置复杂度是多少这个我们马上算。1.2 暴力做法的复杂度噩梦假设N最大是5000M最大是10000甚至更大。每出现一对关系最坏情况下区间跨度接近N也就是一次修改要遍历将近5000个位置。M次操作就是5000×10000五千万次简单操作看着好像还行但如果N和M都到10^5级别呢那就是10^10无论如何都过不去了。这就是差分的用武之地。差分数组的经典场景正是“多次区间修改最后一次查询”也就是把“给区间[l, r]内每个元素加一个常数”这件事从O(区间长度)优化到O(1)。注意这里的关键限制条件修改操作很多但查询是在所有修改结束之后统一做的不是边修改边查询。这道题完美符合这个特征M个关系全部读完然后一次性输出每头牛的高度。打个比方你给一整排书架上的书都贴上标签如果一本一本贴几百本书还能接受几万本就累死了。但如果你有一个办法只在书架两端做个记号最后统一结算的时候根据这些记号推算出每本书该贴什么标签那就轻松多了。差分就是这个“只在两端做记号”的办法。2. 差分数组原理一次搞懂前缀和的逆运算2.1 差分到底是什么先复习一下前缀和。一个数组a从头到尾累加得到前缀和数组s其中s[i]表示a[1]到a[i]的和。差分就是逆操作给定数组a我们构造一个数组b使得b[i] a[i] - a[i-1]规定a[0] 0。这样b就记录了a中相邻元素的差值而a本身就是b的前缀和。举个例子a [2, 5, 3, 8]对应的差分数组b [2, 3, -2, 5]第一个数不变因为a[0]0。验证一下b的前缀和223523(-2)323(-2)58。确实还原了a。这里的核心关系就是差分数组的前缀和 原数组。这就是为什么说差分是前缀和的逆运算。看起来平平无奇妙处在于区间修改。假设我想让a数组从第2个位置到第3个位置的元素都加1变成[2, 6, 4, 8]。那新的差分数组是[2, 4, -2, 4]跟原来的差分数组[2, 3, -2, 5]一比注意看变化b[2]从3变成了4加了1b[4]从5变成了4减了1。中间其他位置完全没变。这就是差分的核心操作想给原数组[l, r]区间内的每个元素加一个常数x只需要在差分数组上让b[l]加x、b[r1]减x。原理也简单因为差分数组的前缀和就是原数组如果b[l]加了x那么从l开始的前缀和都会多出x直到遇到b[r1]减了x才抵消掉。这样一次区间修改就变成了差分数组上的两次单点修改从O(len)变成O(1)。2.2 为什么这道题要“减1”而不是“加1”回到“最高的牛”这道题。我们假设所有牛初始都是最高高度H然后每出现一对关系(a, b)就说明区间(a, b)内部的牛必须比两端矮。怎么用差分体现“矮”关键在于区间内每头牛至少要比两端的牛矮1个单位。所以我们可以这样想——先把所有牛都设定为H这是一种“最大可能值”的初始状态。然后每来一个关系就把区间内部的牛全部减去1表示它们受到了“限高”限制。最后每头牛的高度就是H - 它被减掉的次数。减掉的总次数都是通过差分数组累计的。初始时差分数组全为0表示所有牛高度都还是初始的H。每遇到一组关系比如关系(1, 5)就把区间[2, 4]内的牛全部减1也就是在差分数组上让d[2]减1、d[5]加1。注意区间端点如果a和b能互相看见那么它们之间的牛是a1到b-1要减的是中间这些位置不包括a和b本身。最后对差分数组做前缀和得到这个“减的次数数组”cc[i]表示第i头牛总共被减了几次。第i头牛的可能最大高度就是H - c[i]。这里有一个重要直觉题目要求的是“可能的最大高度”我们一开始给每头牛都赋了最大可能值H然后每次约束都尽最大可能少减每组关系只减区间内的牛所以最后得到的高度就是满足所有约束的最大高度。2.3 关系里的“重复”和“包含”问题题目给的关系可能重复。比如给了关系(1, 5)又给了关系(1, 5)如果不去重等于把区间减了两次最后导出的高度会比正确值矮。这显然不合理因为同一组牛能互相看见是一条事实事实重复说几遍也不会让中间的牛变得更矮。再比如关系(2, 8)包含关系(3, 7)如果两个都处理中间区域会被减两次。但逻辑上(3,7)的约束说中间牛必须矮于3和7(2,8)的约束说中间牛必须矮于2和8假设2号牛和8号牛都比较高那这两个约束是同时成立的中间牛确实要同时满足这两个限制。所以包含关系不能随便去重只能把完全相同的关系去掉。实现去重最省事的办法是用一个二元组的集合set或者unordered_set每次都把pair(a, b)塞进去遍历完集合再统一处理。因为a和b谁在前不影响关系所以插入前先保证a b统一格式。我习惯用setpairint, int排序去重一步到位虽然unordered_set更快但在这种题里set完全够用也让调试时能看到顺序。3. 核心细节解析与实操要点3.1 关系去重与区间方向统一去重之前要做的一件事把每一对关系里的两个数排好序。因为题目输入的关系可能是(5, 1)这种写法直接塞进set的话(1,5)和(5,1)会被当成两个不同的二元组就没法去重了。所以统一处理成(a, b)其中a b。这样(1,5)和(5,1)都会被存成(1,5)set自动去重。去重这件事别看简单很多新手在这里卡住。如果不去重反复出现的关系会让中间区域的牛被多减最终高度偏低。测样例时可能发现不了因为样例里一般没那么多重复但大数据一跑就原形毕露。我甚至见过有人在这题卡了半天最后发现是去重没做同一个二元组被算了两次。3.2 区间端点的正确选取有了关系(a, b)之后要减的是区间(a1, b-1)内的牛。为什么不是(a, b)因为a和b这两头牛本身是“能互相看见”的那两头它们的头顶不是被限制的对象。如果错误地把端点也算进去就会导致这两头牛高度也变矮跟“最高的牛是H”这个设定冲突如果最高的牛自己被减了最后输出就不是H了直接错。边界情况要小心如果a和b紧挨着也就是b - a 1那么区间(a1, b-1)是空的根本不用处理。这种情况在代码里其实可以自然跳过因为差分更新的两个端点位置会重合——等一下这里要注意实际上如果l a1, r b-1当l r的时候说明区间为空。但更严谨地说如果l r 1我们就不应该做任何操作。你可以专门判断一下但即便不做判断直接执行只要写成对区间[l, r]做操作并且实现里用的是“d[l] - 1; d[r1] 1;”当r l时本质上两个操作都不是针对有效区间的会造成问题。稳妥起见if (l r) 才操作。还有一个容易踩的坑差分数组的下标范围。我们开的是N2左右大小的数组对区间[l, r]减1的操作用的是d[l] - 1d[r1] 1。当r等于N的时候r1就是N1所以数组要开到N2不然越界。很多人在小数据上没事数据一大就数组越界报错还莫名其妙。写题的时候直接把数组开成N 5多出来的几个位置当缓冲区省心一辈子。3.3 最高的牛的编号和高度并不会被特殊处理题目里给了“最高的牛是第P头高度为H”。很多新手觉得既然最高牛在第P位置那这个位置是不是要特殊处理其实完全不需要。我们的差分更新只作用于“被约束的区间内部”最高的那头牛如果处于某段关系内部说明它也比两端矮这不可能但它如果真的处于内部那就说明题目给出的关系不可能包含它作为被约束方或者说如果约束中出现与最高牛有关的区间规律上也能保证它的高度不会被压低。为什么因为最高的牛高度是H是所有牛里最高的。如果关系(a,b)的区间内部包含这头最高的牛那么这头牛就必须比a和b矮矛盾。而合法数据保证不会出现这种自相矛盾的情况。所以最高的牛永远不会出现在任何区间的内部它只会作为端点出现。这样一来它永远不会被减最后输出H完美符合题意。这就是为什么我们完全不用特判它只要正常处理所有关系就行了。3.4 初始化与输出为什么初始差分全0就对了另一种理解方式我们给每头牛初始赋值为H然后对受约束的区间减1。那么这个“初始赋值H”的数组对应的差分数组是什么是d[1] Hd[N1] -H其余全0因为初始数组每个位置都是H相邻差值只有第一处是H第N1处是-H。但我们在代码里通常直接开一个全0的差分数组只记录“减的次数”最后统一用H去减。这个二选一的思路要搞清楚不然很容易混。推荐做法差分数组d全0表示初始“减的次数”全是0。每来一个关系记录区间内部需要减1在d上做两次单点修改。最后做一遍前缀和得到c[i]减的次数答案就是H - c[i]。这样做的好处是数字比较小不会特别解释说清楚就是代码干净。如果直接模拟初始H的差分代码里还要处理d[1]H、d[N1]-H这些边界容易出错。我一致推荐用“记录减少次数”的版本。4. 实操过程与核心代码实现4.1 完整代码逐段拆解下面直接给出一份C完整实现我把注释写详细一点对照着看更好懂。#include bits/stdc.h using namespace std; const int N 100005; int d[N]; // 差分数组记录减少次数 int main() { int n, p, h, m; cin n p h m; setpairint, int st; // 去重 for (int i 0; i m; i) { int a, b; cin a b; if (a b) swap(a, b); // 统一左小右大 st.insert({a, b}); // 同一关系只保留一次 } for (auto pr : st) { int a pr.first, b pr.second; int l a 1, r b - 1; // 要减的是两头牛之间的牛 if (l r) { // 只有当区间非空才处理 d[l] - 1; d[r 1] 1; } } // 差分数组转前缀和得到每头牛被减的次数 for (int i 1; i n; i) { d[i] d[i - 1]; cout h - d[i] \n; } return 0; }这段代码就这么短核心逻辑就三块去重、差分更新、前缀和输出。我第一次看到这题题解的时候都惊了一个听起来有点绕的题代码竟然这么短。但短不代表简单里面的几个细节想明白才是真的会了。4.2 手推一个小例子验证流程光看代码不够拿个具体例子走一遍。假设n5p3h10m2关系分别是(1,3)和(3,5)。注意这两组关系都跟最高的牛假设在3号位高度10有关但3号牛只是作为端点出现不是区间内部的牛。先看(1,3)区间内部是[2,2]所以2号牛被减1次更新d[2]-1d[3]1。再看(3,5)区间内部是[4,4]所以4号牛被减1次更新d[4]-1d[5]1。最后做前缀和d初始全0经过两次更新d [0, 0, -1, 1, -1, 1]下标1到5d[6]也用得上但这里不越界就行。前缀和之后1号0高度102号-1高度93号0高度104号-1高度95号0高度10这个结果对不对验证一下1号和3号互相看见中间的2号是9低于10OK。3号和5号互相看见中间的4号是9低于10OK。5头牛里最高的确实是3号的10虽然1号和5号也是10但题目只要求最高牛是H没说不能有并列最高。结果完全正确。4.3 复杂度分析从O(NM)到O(NM)暴力做法的时间复杂度是O(NM)因为每组关系都可能遍历整个区间。差分做法的复杂度是读入和去重O(M log M)set操作带log差分更新O(M)最后前缀和O(N)。总体O((N M) log M)或者干脆说O(M log M N)空间O(N M)。在N和M都是10^5甚至10^6级别的题目里这个复杂度就是标准的“扫一遍”级别绝对够用了。这也是为什么差分数组在处理“多次区间修改最终单点查询”的题型里是首选方案。如果题目变成了“边修改边查询”那就要上树状数组或线段树了这是后话。5. 常见问题与排查技巧实录5.1 为什么我的答案总是比样例矮1这是最经典的错法把区间端点也算进去了。比如关系(1,3)我一开始错误地让区间[1,3]里的牛全部减1导致1号和3号这两头能互相看见的牛高度被压低了。最后输出里端点的高度不是H而是H-1。每次都差1样例一对就能发现但如果只盯着代码看就是反应不过来。所以记住能互相看见的两头牛本身不被减被减的是它们之间的牛。5.2 同一对关系出现两次要不要处理不要。同一对关系是重复信息不影响约束强度。用set去重是标准的做法。但也要小心不能把所有“看起来差不多”的关系都去重。比如(1,5)和(2,4)前者区间大后者区间小都处理才是对的因为它们是两个不同的约束不能合并。如果不用set也可以排序后扫一遍跳过相邻重复项但set更省事。注意setpairint,int的pair比较是字典序的自动完成左小右大排序也方便后面统一遍历。5.3 差分数组要开多大开N5或者N10最稳。这道题里更新操作会用到r1下标当rN时会访问d[N1]所以数组大小至少N2。有人开到N就报运行时错误改大一点就过了。这几乎是差分题最常见的“灵异错误”我都是直接开大点养成好习惯。5.4 如果区间是空的怎么办也就是a1 b-1比如(1,2)或(2,3)。这两头牛紧挨着中间没有牛不需要做任何操作。代码里用if (l r)挡住就行。如果不挡你会让d[2]减1、d[2]加1因为l2, r1时r12两个修改重合抵消其实也没事但写个判断更清晰也避免自己调试时胡思乱想。5.5 为什么前缀和之后可能有负数差分数组里存的是负数比如-1前缀和之后得到的是“减少次数”比如-1表示减少1次。输出时是h - d[i]注意d[i]此时是负数比如h10d[i]-1那么输出11不对这里要小心。等一下这是最容易绕晕的地方让我仔细说。我们前面定义的d数组初始全0每对一个区间[l,r]减1就d[l]-1d[r1]1。这样d里面存的是负数是的。前缀和之后d[i]会变成负数比如-1、-2之类表示第i头牛总共被减去了几次。输出应该是h d[i]还是h - d[i]来推一下如果2号牛被减了1次前缀和后d[2]应该是-1。高度应该是10 - 1 9而h - d[i] 10 - (-1) 11错了。所以正确写法应该是h d[i] 10 (-1) 9。或者另一种实现差分更新时用d[l] 1, d[r1] - 1前缀和后d[i]是正数比如1高度就是h - d[i]。对就是这个区别。我在上面代码里写的是d[l] - 1; d[r1] 1那么前缀和后d[i]是负数输出要用h d[i]。但我代码里写的是h - d[i]回头检查一下……我前面给的代码片段里写的是cout h - d[i] \n;这跟前面的更新方式不匹配。如果更新用d[l] - 1前缀和后d[i]为负输出应该是h d[i]。为了代码读起来自然更推荐的做法是更新时d[l] 1d[r1] - 1这样前缀和后d[i]表示“减的次数”是正数输出h - d[i]就顺理成章。让我把这个问题理清楚写正确的版本。这也是实战里特别容易犯的一个符号错误值得单独拎出来说。所以最终代码应该是for (auto pr : st) { int a pr.first, b pr.second; int l a 1, r b - 1; if (l r) { d[l] 1; d[r 1] - 1; } } for (int i 1; i n; i) { d[i] d[i - 1]; cout h - d[i] \n; }5.6 如果题目里的P最高牛的编号根本用不到对P在这个解法里确实用不到。你读进来之后可以不存或者存了不用。这让很多初学者困惑但仔细想想就明白了我们用的“所有牛初始为H”的设定已经隐含了“最高牛是H”这个信息。而合法的输入保证最高的牛一定在P位置其他牛无论如何都不会超过H。所以P只是保证数据合法的背景设定不需要参与计算。如果说得更直白一点哪怕你不知道P是几只要输入关系是合法的用上面的算法照样能得出正确答案。我试过把P从输入里抠掉结果完全一样。这算是一个比较反直觉的观察理解了这一点对差分“只记录减少量、初始都是最大值”的思路会有更深的认识。6. 差分思维的延伸与应用场景6.1 差不只是数组技巧更是一种“延迟计算”思想当你把“区间操作”拆成“两端标记、最后统一扫描”的时候你其实在用一种叫“延迟计算”或者说“懒标记”的思路。这种思路在线段树里变成lazy tag在差分约束里变成前缀和处理在很多图算法里也有影子。学会了差分再学线段树的lazy propagation会轻松很多因为它们共享同一个思维内核不要每次都老老实实更新所有位置而是把更新“欠着”等到最后统一结算。再往深了说差分数组是前缀和数组的逆运算而前缀和本身就是很多问题的基本工具。如果你想加深理解可以试试把差分用在一维数组之外的场景——二维差分用于矩阵区域加减树上差分用于路径操作。有一次我在做树剖题的时候发现树上的路径修改用树上差分可以少写几十行代码那种感觉真的很好。6.2 差分思想在硬件与信号处理里的影子有意思的是“差分”这个词在别的领域也有它的含义而且内核思想非常接近。比如差分信号、差分放大电路、差分运算放大器——这些硬件设计里“差分”就是取两个信号之差把共模干扰抵消掉。这和算法里的差分数组有异曲同工之妙差分数组存的是相邻元素之差你在输出的时候做前缀和能还原出原始信息而差分电路直接对两路信号的差做放大能去掉两路信号共同携带的噪声。再看差分隐私算法它是在查询结果里加噪声让攻击者无法区分真实数据和扰动数据但这个“加噪声”本质上也是一种对数据差别的处理。差分方程的数值解法同样是利用相邻采样点的差值来逼近微分。所以说“差分”是一个跨领域的基础思想理解了它在算法里的用法再去碰任何带“差分”两个字的概念都会有一种熟悉的底气。这也算是我刷题之外的额外收获吧。6.3 配套练习建议如果你想用这道题练熟差分我建议做三件事。第一把代码里的set换成排序去重再手写一遍加深对去重逻辑的理解。第二自己出几组随机数据用暴力和差分实现各跑一遍对拍验证这个过程能帮你发现所有隐秘的边界错误。第三找几道同样是“区间操作”的经典题练手比如“区间加常数后求最终数组”的模板题、二维差分模板题、树上差分模板题把这一个知识点的应用面彻底铺开。我个人经验是差分这种基础工具光看题解是记不住的必须自己写个三五遍写到闭着眼睛都能把d[l] 1、d[r1] - 1这个套路默出来才算真的会了。写完这题之后再遇到任何“区间统一变化最后输出结果”的题你都应该条件反射地想到差分数组这就到位了。