企业官网建设流程全解析

最近在刷题群里聊天，发现很多小伙伴看到“前缀和”“差分”这两个词就自动开启了恐惧模式，总觉得这是什么高大上的高级数据结构。其实我真想拍拍你们的肩膀说一句：兄弟，这不就是你高中玩剩下的 Sn 和 an 吗？数学课上那个让你又爱又恨的数列前 n 项和，搬到程序里换了个马甲，居然就唬住了一堆人。

今天这篇不整虚的，我陪你把前缀和与差分这层窗户纸捅破。你会发现它们一个是 Sn 给 an 做减法，一个是 diff 数组做加法，思路全在高中数学里。学完之后，区间求和、区间修改那些动不动就超时的题，基本就是送分题了。不管你是刚入门算法的小白、准备面试的校招生，还是带学生的竞赛教练，这篇都能给你一点实际有用的东西。

1. 把 Sn 和 an 请出来，算法恐惧症先治一半

1.1 高斯的 1 加到 100，其实就是前缀和的雏形

先回忆一个小故事。高斯 7 岁那年，老师让全班算 1+2+3+…+100，别的孩子还在埋头硬加，高斯几秒钟就给出了 5050。他怎么算的？1+100=101，2+99=101，3+98=101，一共 50 组，101×50=5050。

你有没有发现，高斯做的事情，本质上就是放弃逐个累加，通过一个巧妙的“规律”快速得到“前 n 项的总和”。小学他算的是 1 到 100 的累加，到了高中，这个“前 n 项总和”就有了正式的代号——Sn（前 n 项和），而数列中每一项就叫an。

说这里我想敲一下黑板：Sn 和 an 之间有一个最朴素的关系式——an = Sn - S(n-1)。意思是，第 n 项的值，等于前 n 项的和减去前 n-1 项的和。你可以把它理解成，账本上记到第 n 个月的累计总金额，减去记到第 n-1 个月的累计总金额，剩下的就是这个月单独花的钱。

这个式子看着不起眼，却是今天整篇文章的命根子。前缀和、差分、区间查询、区间修改……所有“高大上”的技巧，翻来覆去都是在用这个式子变花样。你高中数学里早就跟 Sn 和 an 打过几百个照面了，现在不过是把数列写进数组里而已。

1.2 把数列搬进数组：前缀和到底是什么

高中数列是 a1、a2、a3……an，程序里叫数组 arr[0]、arr[1]、arr[2]……arr[n-1]。名称换了一下，本质完全一样。

给定一个数组 arr，我们新开一个数组 pre，让pre[i] = arr[0] + arr[1] + … + arr[i]。这个 pre 数组就是传说中的前缀和数组。名字取得很直白：每个位置存的是从开头到这个位置的“前缀”的累加和。

举个例子。arr = [3, 1, 4, 1, 5]，那么：

• pre[0] = 3
• pre[1] = 3 + 1 = 4
• pre[2] = 3 + 1 + 4 = 8
• pre[3] = 3 + 1 + 4 + 1 = 9
• pre[4] = 3 + 1 + 4 + 1 + 5 = 14

你看到没有，pre 数组从头到尾扫一遍就建好了，每个数只用加一次，时间复杂度 O(N)。这就是你给我一个普通数组，我“送还”你一个前缀和版本的数组。它的灵魂不是建出来给你看的，而是建出来以后可以快速回答“任意一段的和是多少”这个问题。这个等会细说，你先记住 pre[i] 的定义就够。

1.3 反过来操作：差分数组是不是也眼熟

既然 an = Sn - S(n-1)，那我把思路倒过来。现在手动构造一个数组 diff，使得原数组 arr 正好等于 diff 的前缀和，也就是arr[i] = diff[0] + diff[1] + … + diff[i]。那 diff 数组应该怎么填？直接拿差就行：diff[i] = arr[i] - arr[i-1]，其中 diff[0] = arr[0]。

还是用 arr = [3, 1, 4, 1, 5] 来试：

• diff[0] = 3
• diff[1] = 1 - 3 = -2
• diff[2] = 4 - 1 = 3
• diff[3] = 1 - 4 = -3
• diff[4] = 5 - 1 = 4

所以 diff = [3, -2, 3, -3, 4]。你现在做一个验证：把 diff 从头累加，3 + (-2) = 1，再加 3 = 4，再加 (-3) = 1，加 4 = 5，走一遍正好还原出原数组 [3, 1, 4, 1, 5]。

这就是差分数组：它存的是原数组相邻两项的“变化量”。前缀和是“从部分到整体”的累积，差分是“从整体抠局部”的差值，两者天然互逆。高中里你是不是还学过“已知 Sn 求 an，已知 an 求 Sn”？一模一样的关系，一个正着算，一个反着推。

2. 前缀和有多香：区间求和从 O(N) 秒变 O(1)

2.1 暴力为什么撑不住：一个真实的统计场景

假设你在做一个网页访问统计系统，每天记录一次访问量，得到一个数组。产品经理隔三差五就来问：“上周一到这周三，总共多少访问量？”一次两次还好，次数多了你会发现，每次都得循环把区间里的数加起来。

更扎心的是产品经理通常一次性给你几十个区间，每个区间长几千甚至上万。等你把所有区间算完，肉眼可见的卡顿就来了。整体算下来复杂度是 O(N×M)，N 是数组长度，M 是区间个数。数据规模一上去，超时在所难免。这就是算法的意义——不是炫技，是为了不挨产品经理的骂。

2.2 一手前缀和，区间求和变成一道减法题

前缀和解决这个问题的思路特别清奇。既然需要反复求区间和，那就提前把所有“从开头到每个位置的和”存好。然后直接用公式：

sum(l, r) = pre[r] - pre[l-1]

这个公式怎么来的？pre[r] 是前 r 项和，pre[l-1] 是前 l-1 项和，一减，正好剩下第 l 项到第 r 项的和。这里唯一要小心的是 l=0 的边界，一般我习惯把数组从下标 1 开始存，或者如果下标从 0 开始，边界就单独判断。

用刚才的数组 arr = [3, 1, 4, 1, 5]，pre = [3, 4, 8, 9, 14]。现在要查第 2 个到第 4 个元素的和（注意下标从 0 数），也就是 4 + 1 + 5 = 10。用公式：pre[4] - pre[1] = 14 - 4 = 10，完全正确。

一次查询 O(1)，一百万次查询就是一百万次减法，再也不会超时。你是不是突然觉得，原来算法题里那些“数据结构优化”，有时候就是一道初中减法？

2.3 二维前缀和：从一维小河流到二维大湖

一维整明白以后，二维其实顺理成章。矩阵中左上角到某个点围成的矩形所有元素之和，就叫二维前缀和。它解决的是“子矩阵求和”的问题。

计算公式稍微复杂一点，但用的还是容斥原理：

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

为什么要减去 pre[i-1][j-1]？因为加了两遍左上角那一块，必须减掉一个，不然就重复了。这就跟你算两个有重叠区域的圆的总面积一样，重叠区要扣一次。

查子矩阵 (x1, y1) 到 (x2, y2) 的和时，依然是容斥：

sum = pre[x2][y2] - pre[x1-1][y2] - pre[x2][y1-1] + pre[x1-1][y1-1]

我第一次看这个公式的时候，画了半天图才彻底理解。建议你也动手画一个 3×3 的小矩阵，把每个 pre 值标上去，然后实际减一遍，比干看公式高效十倍。二维前缀和常用于图像处理里的区域灰度求和、游戏地图上的区域统计，以及各种矩阵类算法题，掌握了就是通用技能。

3. 差分上场：区间修改的 O(1) 魔法

3.1 给区间集体加值，暴力累加能不能优化？

有求和的难题，自然也有“修改”的难题。给定一个数组，频繁执行“把第 l 到第 r 个元素都加上 v”。暴力做法再清晰不过了：从 l 循环到 r，每个位置加 v。一次操作 O(N)，M 次操作 O(N×M)，同样说超时就超时。

这种场景现实中太常见了。游戏服务器里给一批玩家统一发奖励，每个人的积分落在某个区间；在线课程系统给学生批量加平时分；统计系统给某段时间的日志统一打标记。全都是“一个区间、一次操作、整体修改”的套路。差分数组，就是为了这一招而生的。

3.2 核心思想：把“改区间”变成“改边界”

我们回忆一下 diff 数组的定义：diff[i] = arr[i] - arr[i-1]，而且原数组等于 diff 的前缀和。注意，既然是前缀和还原，那 diff 上某个位置的变化，会影响“从这个位置开始往后的所有原数组位置”。利用这个性质，就出现了神仙操作：

对原数组的区间 [l, r] 统一加 v，等价于：

• diff[l] += v
• diff[r+1] -= v（注意是 r+1，别写成 r）

就这两行，区间修改变成 O(1)。原理很简单：diff[l] 加了 v，前缀和还原的时候 arr[l]、arr[l+1]……全都会跟着加 v，一直影响到数组结尾；但我们要影响在 r 就停住，所以 diff[r+1] 减掉 v，让 arr[r+1] 及以后的位置又恢复原值，整体净影响就只落在 [l, r] 上。

拿 arr = [3, 1, 4, 1, 5] 再演示一次。先求 diff = [3, -2, 3, -3, 4]。现在执行“下标 1 到 3 全加 2”：

• diff[1] += 2，变成 0
• diff[4] -= 2（因为 r+1 = 4），变成 2

新的 diff = [3, 0, 3, -3, 2]。对着它做前缀和还原：3，3+0=3，3+0+3=6，再加 -3=3，最后 +2=5。得到 [3, 3, 6, 3, 5]，看原数组 [3, 1, 4, 1, 5] 下标 1 到 3 的 1、4、1 确实都加了 2，变成 3、6、3，其他位置纹丝不动。成了。

3.3 差分和前缀和，其实是同一条路的两面

很多人学了前缀和又学差分，总觉得是两个东西，其实它们就是同一条路正着走和反着走。前缀和数组由原数组递推得到，差分数组由原数组递推得到；原数组是差分数组的前缀和，差分数组是原数组的差分。

你可以这样对比着记：

这就像同一个硬币的正反面。遇到“区间求和”的题往前缀和想，遇到“区间修改，最后再查”的题往差分想。这两种套路交叉使用，能解决非常多的经典问题。

4. 再加点猛料：二维差分和前缀和的花式玩法

4.1 二维差分：给整个子矩阵打标记

一维差分学会了，二维差分其实就是它的“矩阵版”。它解决的是“给某个子矩阵的所有元素统一加上 v，最后求最终矩阵”的问题。常见于模拟游戏中区域效果，比如一个技能覆盖矩形范围，范围内所有格子扣血，范围外不受影响。

构造二维差分数组 diff 的公式，跟二维前缀和刚好是镜像关系：

• 构建时对原矩阵求二维差分（即相邻行、相邻列都给差值）
• 修改时操作四个角落：

假设给左上角 (x1, y1)、右下角 (x2, y2) 的矩形区域加 v：

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

第一次看到这个四个点的操作，你大概率会觉得“这谁能想到啊”。其实别慌，它可以理解成二维的边界标记法：第一处在起点开启“影响”，第二处第三处在两条边界截止“影响”，第四处把被减去两次的角落补回来。这跟二维前缀和的容斥原理是完全对称的。

最终要还原矩阵时，对 diff 做二维前缀和，得到的 pre 矩阵就是修改后的真实矩阵。建议你亲手写一遍这四个点加 v，然后做一次前缀和，打印出来对比一下，印象会刻进脑子里。

4.2 差分约束系统：把不等式组变成最短路径

如果你往后刷题刷深了，会碰到一个叫“差分约束系统”的进阶话题。它跟差分数组有关系但又不完全一样：给定一堆形如 xi - xj <= c 的不等式，要求一组满足条件的解。这个问题的经典解法是把每个变量看作图的节点，把不等式看作一条有向边，然后跑最短路算法。

我第一次看到这个转化的时候也愣了半天，后来想通了：不等式 xi - xj <= c，不就是图上 j 到 i 有一条权重为 c 的边吗？在差分约束里，每个约束都代表距离关系的上限，最短路算法求出来的就是满足所有约束的变量值。前缀和与差分解决的是数组上的区间问题，差分约束解决的是不等式组求解问题，名字像，内核还得靠你慢慢体会。不过能走到这一步，说明你已经不是菜鸟了。

4.3 前缀和的隐藏技能：配合哈希表解决“和为 k 的子数组”

前缀和不仅能做区间求和，还能玩出别的花。比如经典问题“统计和为 k 的子数组个数”。如果暴力枚举所有子数组，复杂度 O(N^2)，数据一大就吃不住。

用前缀和加哈希表的思路很巧妙。遍历数组的过程中，维护当前前缀和 cur。要是存在一个位置 j，使得 cur - pre[j] == k，那就说明从 j+1 到当前位置这一段的和正好为 k。所以只需要用一个哈希表统计每个前缀和值出现的次数，在遍历时查询 cur - k 出现过几次，累加上去就行。

换句话说，以前你要枚举“每个起点 + 每个终点”去验证，现在只需要一边算前缀和一边查哈希表，O(N) 搞定。我刷题时有阵子遇到这种“找连续子数组满足某种条件”的题，第一反应就是前缀和 + 哈希，命中率极高。

5. 实战拆题：三道经典题带你彻底上手

5.1 LeetCode 303：区域和检索，数组不可变

这道题是前缀和的标准模板题，我建议每个人都手敲一遍。题目给你一个整数数组 nums，反复调用 sumRange(i, j) 求下标 i 到 j 的和。

暴力版就是一个循环一个循环地加，每次查询 O(N)。但题目通常会疯狂调用查询接口，所以必须用前缀和预处理。

我的做法是维护一个长度为 n+1 的前缀和数组 pre，其中 pre[0] = 0，pre[i+1] = pre[i] + nums[i]。这样下标刚好错开一位，区间和直接返回 pre[j+1] - pre[i]，不需要额外处理 i=0 的边界。

class NumArray: def __init__(self, nums): self.pre = [0] * (len(nums) + 1) for i in range(len(nums)): self.pre[i + 1] = self.pre[i] + nums[i] def sumRange(self, i, j): return self.pre[j + 1] - self.pre[i]

代码量就这么点，但你把这一题吃透了，一维前缀和基本就过关了。我当年第一次写这个题，还傻傻地在构造方法里不存 pre，结果查询次数一多就超时，后来才意识到预处理才是精髓。

5.2 LeetCode 1109：航班预订统计

这题是差分数组的入门神题。有一张航班预订表，每条记录是 bookings[i] = [first, last, seats]，表示“从 first 航班到 last 航班，每个航班都要加 seats 个座位”。最后要返回每个航班的总座位数。

看到“区间内每个位置统一加一个值”，这就是差分数组的信号，几乎不需要犹豫。起飞的航班号从 1 开始，我直接把 diff 数组做成 n+2 大小，这样 r+1 减 v 的时候不会越界。

def corpFlightBookings(self, bookings, n): diff = [0] * (n + 2) for first, last, seats in bookings: diff[first] += seats diff[last + 1] -= seats ans = [] cur = 0 for i in range(1, n + 1): cur += diff[i] ans.append(cur) return ans

这个题我把 diff 构造完以后，会手推一遍“前缀和还原”的过程，确保自己不是背模板而是真的明白为什么 diff[first] += seats、diff[last+1] -= seats。你要是能把每一步都讲清楚给旁边的人听，这题就真学会了。

5.3 LeetCode 304：二维区域和检索，矩阵不可变

一维搞完就该上二维了。LeetCode 304 要求快速回答子矩阵的和，这个必须用二维前缀和。

我的代码习惯是给 pre 数组多扩一行一列，pre[i][j] 表示“原矩阵第 0 行到第 i-1 行、第 0 列到第 j-1 列围成区域的和”，这样下标从 1 开始，四个角的边界判断统统消失，代码写起来真的神清气爽。

class NumMatrix: def __init__(self, matrix): if not matrix: return m, n = len(matrix), len(matrix[0]) self.pre = [[0] * (n + 1) for _ in range(m + 1)] for i in range(m): for j in range(n): self.pre[i + 1][j + 1] = ( self.pre[i][j + 1] + self.pre[i + 1][j] - self.pre[i][j] + matrix[i][j] ) def sumRegion(self, r1, c1, r2, c2): return ( self.pre[r2 + 1][c2 + 1] - self.pre[r1][c2 + 1] - self.pre[r2 + 1][c1] + self.pre[r1][c1] )

这份代码里那个“容斥”的四个项，我写错了不下五次，每次都是调试的时候才发现加号减号搞反。所以我的体会就是，二维前缀和不难，但特别考细心。写的时候在纸上画一个 2×2 的小矩阵，标清楚 pre 每个格子的值对应原矩阵哪一块，再对照代码看一遍，基本就不会再错了。

6. 常见坑和调试经验：老油条的避坑指南

6.1 边界下标永远是最熟悉的陌生人

前缀和使用 pre[l-1] 时，l=0 会访问到 -1；差分使用 diff[r+1] 时，r 是最后一个元素会越界。很多新手第一遍写这类代码，百分之八十的报错都出在这。

我个人的统一解法就是多开一个位置。前缀和数组长度 n+1，pre[0] 设为 0，后面 pre[i] 存前 i 个元素的和；差分数组长度 n+2，专门让 r+1 有地方落。这个方法简单粗暴，却能省下一整天排查越界的时间。实测下来，比到处写 if 判断要稳得多。

6.2 二维数组别把行列搞混，真不是开玩笑

二维前缀和里的 i、j，一个是行一个是列。我刚学那阵经常在计算 pre[i+1][j+1] 时把 matrix[i][j] 写成 matrix[j][i]，小数据正好矩阵对称，还没报错；一上不对称的大矩阵，结果全崩。

如果你也常犯这毛病，建议变量名用 x、y 来记坐标，并且写代码前先在注释里定义清楚：第一个下标是第几行，第二个下标是第几列。习惯成自然以后，这类低级错误就基本消失了。

6.3 数据范围一大，int 就开始闹脾气

前缀和数组存的是累加值，如果原数组元素是 int 型，累加过程中很容易溢出。尤其是长期服务类的在线系统，数据上亿都不新鲜，随手一个前缀和可能就超出 int 上限。

我在生产代码里一般直接上 long long，刷题时看数据范围，超过 10^5 而且数值较大就果断换 64 位整数。宁可多占点内存，也别让溢出的负数毁掉结果。这个坑我在某次比赛里踩过，交完代码 WA（错答）的一瞬间，血压直接拉满。

6.4 差分的还原时机：是修一次查一次，还是最后集中还原？

差分数组适合的场景通常是：多次修改、最后再统一查询结果。比如航班预订那题，所有预订记录处理完，最后再算一次前缀和还原出每个航班的数量。如果你每修改一次就去还原一次原数组，那差分就失去意义了，又会退化回 O(N×M)。

但如果你需要“修改后立刻查询某一段的值”，那就应该在查询端配合前缀和或其他数据结构，而不是单独用差分硬扛。选对场景，比会写模板重要得多。

6.5 调试技巧：小数据手算，永远是最高效的办法

我调试前缀和、差分的代码时，最喜欢的做法就是构造一个长度 5 左右的小数组，然后在纸上手算出 pre 和 diff 对应的值，再对着代码一行行比对。这个方法比任何调试工具都好用，因为算法本身不复杂，出错基本都是公式细节，手算一遍立刻就能定位。

打个比方，二维前缀和的容斥公式，你要是只是盯着代码发呆，看半天也想不出问题在哪；但只要把 3×3 的矩阵值写在纸上，用笔圈出 pre 数组每个格子对应的区域，四个项对不对一目了然。

调完以后把纸留着，下次忘了再翻出来看。有时候最土的办法，恰恰是最快解决问题的办法。

7. 写在最后的一点体会

前缀和和差分这两个技巧，说起来也就几行代码的事，但我刷了这么久题，发现它们是真真正正的高频考点和工程利器。很多看似复杂的区间统计问题、批量更新问题，剥开外壳，内核就是这两个思想在打底。

我的建议是别死背模板。刚开始照抄没关系，但抄完一定找几个变体题练，比如把区间求和变成“求奇偶和”、把区间修改变成“区间赋值”、把一维变成二维。练的时候多问自己一句：这一步为什么要这么做？边界条件在哪里？如果把数据类型换一下会怎样？这样折腾几次，你才真正把 Sn 与 an 的关系内化成了自己的武器。

最后再说个实在的：遇到新的题目，先别急着套模板，先画个小例子，用手算几遍，再落代码。刚开始确实慢，但慢就是快。算法这条路，最怕的不是笨，而是怕被名字吓住，永远不敢迈第一步。