企业官网建设流程全解析

如果你刷过和数组区间操作有关的算法题，大概率遇到过这样的场景：有 m 次操作，每次都把区间 [l, r] 里的所有元素统一加上一个数，最后让你输出整个数组。刚入门时最容易想到的办法就是一个 for 循环直接遍历区间逐项修改，代码写起来很顺手，但数据量一大就立刻现出原形——操作次数和区间长度相乘，复杂度轻松突破千万甚至亿级，O(nm) 的时间根本跑不动。

我第一次被这个场景卡住，是在做一道数据规模给到 10^5 次操作、10^5 个元素的模拟题时。当时用循环改完，一运行，超时超得毫无悬念。后来才认真去搞清楚差分算法这个工具，才发现它把每次区间批量修改压到了 O(1)，整体复杂度变成了 O(n+m)，整个思路一下子清爽了。这篇文章就把一维差分和二维差分完整拆开讲一遍，包括构造原理、模板代码、边界处理和排错经验，希望给还没彻底搞懂差分的人一次讲明白。

1. 从一个“改一堆、查一个”的场景说起：差分到底解决什么问题

1.1 直接循环修改为什么吃亏

先看一个最朴素的需求：给定一个长度为 n 的数组，初始值我们暂时不关心，现在有 q 次操作，每次操作把 [l, r] 范围内的元素全部加上 v。所有操作完成后，输出每个位置上最终的值。

暴力做法没有技术含量，就是循环：

for i in range(l, r + 1): arr[i] += v

乍看没什么问题，但假设 n=10^5、q=10^5，每次操作的区间平均长度也是 10^5，那么总操作次数就是 10^10 次。这个量级在普通编程题里就是纯超时，在实际业务场景里如果频繁做这类累计更新，也会很快把性能拖垮。问题不在于“加法本身慢”，而在于我们真的执行了每一个元素的加法——但很多元素在被修改之后，后续再也没有被单独查询过，这些计算本质上是白做的。

1.2 换一个角度：把“值”换成“变化”

这里的核心思维转变是：我们不要盯着每个位置的最终值，而是盯着“相邻两个位置之间的差值”。一个数组一旦确定了首元素的值，以及每个位置相对前一个位置的差值，整个数组就被完全确定了。这个差值序列就是差分数组。

反过来，如果我知道了差分数组，我可以通过一次从头到尾的累加，把原数组还原出来，这个累加操作就是前缀和。所以差分和前缀和是一对互逆操作：对差分数组做前缀和得到原数组，对原数组做差分得到差分数组。这个关系不是死记硬背的模板，而是理解差分一切代码的钥匙。

2. 一维差分：把区间修改变成两个端点的标记

2.1 差分数组怎么构造

假设原数组是 a，下标从 1 开始，为了方便统一处理边界，我们定义差分数组 d，使得：

d[i] = a[i] - a[i-1]

特别地，d[1] = a[1] - a[0]，这里 a[0] 视为 0。从一个数组构造差分数组的代码非常简单：

d = [0] * (n + 2) for i in range(1, n + 1): d[i] = a[i] - a[i - 1]

构造完之后你会发现，如果我们把 d 做一遍前缀和，就能完整还原出 a：

for i in range(1, n + 1): d[i] += d[i - 1] # 此时 d[i] 就是 a[i]

这个还原过程极其重要，因为后面所有的区间修改，都是通过修改 d 来实现的，而最终求答案的时候，再对 d 做一次前缀和，把变化累加回去。

2.2 区间加一个数为什么等价于改两个点

这是整个一维差分最精华的地方。设想我们有一个差分数组 d，现在想把区间 [l, r] 里的每个元素都加上 v。

• 对于 a[l] 来说，它比 a[l-1] 多出来的差值增加了 v，所以 d[l] 需要加 v。
• 对于 a[r+1] 来说，它比 a[r] 多出来的差值减少了 v（因为 a[r] 变大了 v，而 a[r+1] 没变），所以 d[r+1] 需要减 v。
• 区间内部的 d[i]，也就是 l < i <= r 的那些位置，a[i] 和 a[i-1] 都同时加了 v，差值保持不变，所以不需要动。

也就是说，一次区间修改，只影响差分数组中的两个位置。这就把 O(区间长度) 的操作压缩成了 O(1)。我最初理解这一步时老是绕不过来，后来换了个比喻就通了：把差分数组想象成一排台阶的高度差，a 是台阶的绝对高度。如果我把第 l 级到第 r 级台阶整体垫高 v，那么这个区间内部的落差完全没变，只有第 l 级和最前面一级之间的落差变大了，第 r+1 级和它前一级之间的落差变小了，其余位置完全不用动。

2.3 一维差分的模板代码与第一次应用

完整流程分三步：构造差分，执行区间修改，最后前缀和还原。我平时写 C++ 的时候习惯用下面这个结构，数组开大一格，避免 r+1 越界。

#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 100005; ll a[N], d[N]; void range_add(int l, int r, ll v) { d[l] += v; d[r + 1] -= v; } int main() { int n, q; cin >> n >> q; for (int i = 1; i <= n; i++) { cin >> a[i]; // 构造差分 d[i] += a[i]; d[i + 1] -= a[i]; } while (q--) { int l, r; ll v; cin >> l >> r >> v; range_add(l, r, v); } // 前缀和还原 for (int i = 1; i <= n; i++) { d[i] += d[i - 1]; cout << d[i] << ' '; } return 0; }

这里需要特别说明的是构造差分那一段：我没有先存 a 再减，而是直接利用区间修改的思想，把 a[i] 当作一次“只对单点 i 加 a[i] 的修改”，也就是做一次 range_add(i, i, a[i])。这会让理解更统一——任何一次初始值的注入，本质上也是一次区间修改，只是区间长度为 1。

我第一次写完这个代码跑样例，发现结果总是对不上，后来定位到原因：初始化构造差分的顺序和区间修改的顺序混在一起了。如果你先构造完 d，再进行修改，逻辑上没问题；如果你像我一样在构造差分的同时利用 range_add，那就必须保证 d 数组初始是干净的，然后在构造完所有单点之后再统一执行后续操作。这两种方式选一种写清楚就行，别混着来。

3. 二维差分：容斥原理在矩阵上的折叠应用

3.1 二维前缀和是先修课

二维差分的理解，我个人认为比一维上了一个台阶，因为涉及的从“两个端点”变成了“四个角点”，核心依据是容斥原理。在看二维差分之前，二维前缀和必须过关，因为二维差分的构造和还原，本质上就是二维前缀和的逆过程。

二维前缀和的定义是：pre[i][j]表示从 (1,1) 到 (i,j) 这个子矩阵内所有元素之和。它的递推式大家应该很熟：

pre[i][j] = pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1] + a[i][j]

加一个区域再加一个区域，重叠部分被加了两次，所以要减掉。这个“多加的部分要减掉”的思想，在二维差分里会原封不动地出现。

3.2 子矩阵修改的四个角点标记法

现在问题升级了：给定一个 n 行 m 列的矩阵，有 q 次操作，每次把左上角 (x1, y1) 到右下角 (x2, y2) 的子矩阵内所有元素加上 v，所有操作结束后输出整个矩阵。

和一维的思路一样，我们希望把“修改一个子矩阵”也变成只改几个点，然后通过对差分矩阵做二维前缀和来还原结果。二维差分数组我们记为 diff，目标是让 diff 做二维前缀和之后得到最终的矩阵。

关键在于：如果一个子矩阵整体加 v，那么在这个子矩阵内部的相对差值全部保持不变，只有边界处发生变化。具体来说，修改四个点：

diff[x1][y1] += v diff[x2+1][y1] -= v diff[x1][y2+1] -= v diff[x2+1][y2+1] += v

为什么是这四个点？我们一步步推。对 (x1, y1) 加 v，相当于在以它为左上角的整个右下区域都注入了 +v 的“趋势”。但我们的目标不是整个右下区域，而是被 (x2, y2) 截断的子矩阵。于是需要在 (x2+1, y1) 处减 v，把 x1 到 x2 之外的下方区域修正回来；同理需要在 (x1, y2+1) 处减 v，把右方区域修正回来。问题是 (x2+1, y2+1) 这个位置被减了两次，需要再加一次 v 弥补，这就是容斥。

如果还是不容易记住，可以对着图看：加 v 产生了两个方向上的影响边界，两个减 v 各消除一条边界，但右下角的重叠区域被多消除了，所以要加回一个 v。这个“减两次加一次”的模式，和二维前缀和里的加两次减一次刚好对应，互为镜像。

3.3 二维差分的构造与完整代码

构造二维差分矩阵时，可以把矩阵中每一个元素 a[i][j] 都看作一次单点修改，也就是执行一次add(i, j, i, j, a[i][j])。这样构造和理解修改操作就能复用同一段逻辑，不用单独记一套公式。下面给出 C++ 的完整实现：

#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 1005; ll a[N][N], diff[N][N]; void add(int x1, int y1, int x2, int y2, ll v) { diff[x1][y1] += v; diff[x2 + 1][y1] -= v; diff[x1][y2 + 1] -= v; diff[x2 + 1][y2 + 1] += v; } int main() { int n, m, q; cin >> n >> m >> q; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { cin >> a[i][j]; add(i, j, i, j, a[i][j]); } } while (q--) { int x1, y1, x2, y2; ll v; cin >> x1 >> y1 >> x2 >> y2 >> v; add(x1, y1, x2, y2, v); } // 二维前缀和还原 for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { diff[i][j] += diff[i - 1][j] + diff[i][j - 1] - diff[i - 1][j - 1]; cout << diff[i][j] << (j == m ? '\n' : ' '); } } return 0; }

这里注意一个细节：add函数内部访问了diff[x2+1][y1]、diff[x1][y2+1]、diff[x2+1][y2+1]，所以二维差分数组的尺寸不能只开 n×m，必须多开一行一列，即至少 (n+2)×(m+2)，否则当 x2 或 y2 到达边界时就会越界。

二维差分的还原就是二维前缀和，上面的递推式和我们在 3.1 里复习过的一模一样。如果你写出来发现数字不对，大概率不是还原公式的问题，而是 add 函数里加减 v 的四个位置写错了，尤其是最后一个容斥的加回操作特别容易漏。

4. 开数组的尺寸选择与下标偏移：我踩过的坑

4.1 d[r+1] 的越界是初学者第一坑

一维差分代码里，d[r+1] -= v这一行看似简单，但当你操作到 r = n 时，d[n+1]就会被访问。如果数组只开了 n 个位置，这里就是越界写，轻则数据错乱，重则直接崩溃。我早期就干过这种事：数组开 n+1，然后操作区间右上角怼到边界，程序没提示崩溃，但输出结果就是不对，查了好几个小时才发现野指针在内存里乱写。

正确做法就是数组一律开 n+2，多出来的两个位置是为 d[n+1] 准备的。二维同理，多出来的那一行一列不只是为了 add 时 x2+1、y2+1 不越界，更是为了让最终前缀和还原时公式完整。数组开大一点不丢人，别在这上面抠内存导致查错浪费大量时间。

4.2 下标从 0 开始 vs 从 1 开始

很多编程题和实际场景里数组下标是从 0 开始的，这时候差分代码需要做小调整。方案有两种：一种是把所有逻辑整体偏移，即修改区间 [l, r]，对应 diff[l] += v、diff[r+1] -= v，其中 r+1 可能等于 n，所以数组需要 n+1 大小；另一种是统一先转成 1-index 处理，输入时下标不减，直接用题目的 1-index 逻辑，最后输出时遍历 0 到 n-1 的部分。

我的个人建议是：除非题目强制要求 0-index，否则一律用 1-index 写逻辑。理由很简单，差分和前缀和的边界公式在 1-index 下最规整，不容易出错；0-index 下差分的概念完全一样，但每个公式都要在心里偏移一次，思维负担变重。实际我用过 0-index 写过二维差分，add 函数的四个位置一旦下标算错半个，整个矩阵就会歪掉。

4.3 二维里 x2+1 和 y2+1 的减法错位

二维差分的四行 add 代码中，最容易写错的是把diff[x1][y2+1] -= v误写成diff[x2+1][y2+1] -= v，或者丢掉最后的diff[x2+1][y2+1] += v。我提供一个记忆方法：把四个点分成两组。第一组是起点相关的 (x1,y1) 加 v，以及它向两个方向扩展的减 v，也就是 (x1,y2+1) 和 (x2+1,y1) 分别减 v；第二组是右下角的交点 (x2+1,y2+1)，它是第一组两个减 v 区域的交集补回，所以加 v。记住“一个加、两个减、一个加回”，手写的时候对着这个节奏检查，基本不会乱。

5. 差分实战的验证方法：造数据和暴力对拍

5.1 直接手算样例永远不够

我见过很多刚学差分的人，代码跑通题目的样例测试就觉得自己会了，结果真正提交或者上生产环境一跑，全盘崩掉。原因很简单：样例往往只覆盖一条路径，边界和重叠情况全都碰不到。差分这种算法，它的正确性高度依赖端点处理，必须用系统化的方式去验证。

我自己最常用的验证方法是写一个暴力版本做对拍。所谓对拍，就是对同一份随机输入，分别跑一遍暴力解法和差分解法，对比两者输出是否一致。只要随机数据量足够大、范围覆盖够广，差分代码里所有隐蔽的边界错误都会暴露出来。

5.2 一维差分的对拍脚本

写对拍不需要什么复杂框架，Python 就能搞定。下面以 Python 为例展示一维差分的对拍思路。先生成随机测试数据，再分别用两种方式计算结果：

import random def brute(n, ops): arr = [0] * (n + 2) for l, r, v in ops: for i in range(l, r + 1): arr[i] += v return arr[1:n + 1] def diff_solve(n, ops): d = [0] * (n + 2) for l, r, v in ops: d[l] += v d[r + 1] -= v for i in range(1, n + 1): d[i] += d[i - 1] return d[1:n + 1] for _ in range(10000): n = random.randint(1, 20) q = random.randint(1, 20) ops = [] for _ in range(q): l = random.randint(1, n) r = random.randint(l, n) v = random.randint(-10, 10) ops.append((l, r, v)) b = brute(n, ops) d = diff_solve(n, ops) if b != d: print("出错啦") print(n, ops) print(b) print(d) break

这里的关键点是随机数据要刻意覆盖边界：l 造到 1，r 造到 n，v 同时包含负数和正数。n 故意控制在 20 以内，确保暴力解法能快速跑完。如果对拍几十轮都没出错，基本可以确定核心逻辑没问题。

5.3 二维差分的对拍验证与制造随机矩阵

二维差分的对拍同理，但随机造数据时要注意子矩阵的左上角必须小于等于右下角，我一般这样生成：

x1 = random.randint(1, n) x2 = random.randint(x1, n) y1 = random.randint(1, m) y2 = random.randint(y1, m)

暴力版本就是四重循环：

def brute_2d(n, m, ops): a = [[0] * (m + 2) for _ in range(n + 2)] for x1, y1, x2, y2, v in ops: for i in range(x1, x2 + 1): for j in range(y1, y2 + 1): a[i][j] += v return a

差分版本与完整 C++ 代码逻辑一致，把 add 的四个 diff 操作照搬过来，最后二维前缀和还原。两版输出逐项比对，一旦不一致，就把这次的输入、暴力结果、差分结果全部打印出来，人工对着算一遍，多半能定位是哪个坐标边界写错了。

对拍这种方法看起来笨，但在调差分这种边缘敏感的逻辑时，效率远比肉眼审查高。我现在的习惯是：任何新写的差分代码，先对拍几百组小数据再谈优化，确保结论可信。

6. 差分不止是模板：从区间操作到差分思维

6.1 树上的差分和时间轴上的差分

一维差分和二维差分是基础，但差分思想绝不止这几种形态。树上差分就是一个非常常见的变体：在一棵树上，给某个路径上的所有节点统一加一个值，最后统计每个节点的值。这个操作可以先用差分标记两个端点和它们的最近公共祖先，最后通过树的遍历把差分值从叶子向根累加，原理和数组差分完全同构，只是累加方向从“数组顺序”变成了“树的结构”。

时间轴上的差分也很有意思。比如一个系统里有 n 个事件，每个事件在某个时间区间内持续生效，我们想判断任意时刻有多少事件在生效，这类问题就可以把每个事件的开始时间 +1、结束时间减 1，然后顺着时间线累加一遍，所有时刻的覆盖数量就都出来了。这个用法在日志分析、日程排重、资源占用统计里都很频繁。

6.2 把“变化量”当作第一思维

差分最有价值的地方，不在于那几个端点修改的公式，而在于它是一种“用变化来描述整体”的思维方式。很多看似需要逐项修改的问题，只要能转换成“只记录起点和终点的变化”，就可以大幅降低复杂度。我处理过一批数据迁移任务，就是对一批记录批量调整某个字段，而每条记录的调整生效时间各不相同，当时直接逐条 update 跑了几十分钟，后来改用“生效时间点记差值、最后按时间累加”的方式，一次跑完只用了不到几秒钟。这就是差分思维的实战收益。

6.3 顺带提一嘴：差分隐私和数组差分不是一回事

因为差分算法相关的文章里经常出现“差分隐私”这个词，我简单说明一下：差分隐私（Differential Privacy）和本文讨论的一维差分、二维差分，名字接近，但内涵不同。差分隐私主要是一种数据发布时保护个体隐私的框架，通过往统计结果里加入经过设计的噪声，让攻击者难以根据输出判断某个个体是否存在。它和数组差分的共同点只在于“关注变化量”这一抽象思路——差分隐私关心的也正是某个个体变化时输出会变化多少——但在技术实现上完全是另一套体系。如果你在看资料时遇到这个词，可以放心地把它当作另一个话题，不要和本文的差分数组混为一谈。

7. 一些最终建议：从入门到真正使用差分的三个层次

先把一维差分的模板代码写熟，做到手写不出错，并理解每行代码修改的是哪个端点的意义；再进入二维，重点吃透 add 函数为什么是“一加二减一加回”，能默写出四行代码；最后进入实战，遇到区间统一修改、最后才查值的题目，先想想能不能用差分，而不是上来就写循环。这个顺序不花哨，但最有效。

以我个人带新人的经验，差分的概念本身不难，难的是两个点：一是真正理解“区间内相对不变、只有边界变”这件事，而不是背公式；二是养成数组开大、边界检查、对拍验证的习惯。如果这两点都做到了，你在差分这一块基本就不会再出错。

最后分享一个我自己的小技巧：写差分代码时，我会在注释里把 diff 数组的含义写清楚——它存的是“当前点相对前一个点的变化趋势”，而不是“最终值”。只要注释里写明这个，过一两个月再回来看代码，不需要从头推理公式也能立刻看懂。这个习惯我保留了好几年，现在回头看很多当时调试了很久的代码，都是因为没留下这种注释。