前缀和与差分

吴老师

2026-10-22 15:54:02

发布于：广东

45阅读

0回复

0点赞

一维前缀和与差分

一、为什么要学习前缀和与差分？

对于一个数组，我们经常需要完成两种操作：

区间查询：求出从第 $l$ 个数到第 $r$ 个数的总和。
区间修改：把从第 $l$ 个数到第 $r$ 个数全部增加或减少某个值。

如果每次都用循环逐个处理，当数组很长、操作次数很多时，程序就会运行得很慢。

为了解决这两个问题，我们需要学习两种算法：

前缀和：快速计算一段区间的总和。
差分：快速给一段区间内的所有数加上同一个值。

二、前缀和

1. 什么是前缀和？

假设有一个数组：

$a=[2,1,3,4,2]$

现在需要计算前 4 个数的总和：

$2+1+3+4=10$

如果每次查询都重新相加，会做很多重复工作。

我们可以提前准备一个数组 $pre$ ，记录从第 1 个数开始，到当前位置为止的总和。

就像记账一样，每天都记录一下到今天为止一共花了多少钱，以后想知道某段时间花了多少，就不用重新计算每一天。

位置 $i$	原数组 $a[i]$	前缀和 $pre[i]$
0	—	0
1	2	2
2	1	3
3	3	6
4	4	10
5	2	12

可以发现：

第 1 个位置的前缀和： $2$
第 2 个位置的前缀和： $2+1=3$
第 3 个位置的前缀和： $2+1+3=6$

每个位置的前缀和，都等于前一个位置的前缀和，加上当前位置的数。

因此：

$\boxed{pre[i]=pre[i-1]+a[i]}$

规定 $pre[0]=0$ ，表示前 0 个数的总和为 0。

2. 如何快速求区间和？

假设要求第 2 个数到第 4 个数的总和。

直接计算：

$1+3+4=8$

利用前缀和，可以换一种思路：

先计算前 4 个数的总和，再减去前 1 个数的总和。

$(2+1+3+4)-2=8$

因此：

$\boxed{sum(l,r)=pre[r]-pre[l-1]}$

这里：

$pre[r]$ ：从第 1 个数到第 $r$ 个数的总和。
$pre[l-1]$ ：区间左边那些不需要的数的总和。

两者相减，剩下的正好就是需要的区间。

这样无论区间有多长，查询时都只需要一次减法。

3. 前缀和代码

// 预处理前缀和
for(int i = 1; i <= n; i++) {
    pre[i] = pre[i - 1] + a[i];
}

// 查询区间 [l, r] 的和
long long sum = pre[r] - pre[l - 1];

注意：

数组从下标 1 开始， $pre[0]$ 必须为 0。
前缀和可能很大，建议使用 long long。
前缀和适合数组不发生修改，或者先完成修改、再统一查询的情况。

4. 课堂练习

第 1 题：A83450 叫号机的区间统计

前缀和模板题。先计算前缀和数组，再利用区间求和公式回答每次查询。

第 2 题：A83453 大树下的阴凉处

寻找长度恰好为 $k$ 的连续区间，使区间和最小。

思路：枚举每一个长度为 $k$ 的区间，利用前缀和快速算出区间和，不断更新最小值。

三、差分

1. 什么是差分？

前缀和解决了快速查询区间和的问题。

现在考虑另一种情况：

给定一个数组，需要多次把一段连续区间内的所有数增加同一个值。

如果每次都使用循环，一个一个地修改，速度就会很慢。

差分可以让我们只修改两个位置，就表示出整个区间的变化。

2. 差分的基本思想

可以把差分想象成一排学生的加分记录。

老师要求从第 2 名到第 4 名学生，每个人增加 3 分。

没有必要提前把这 3 个人的成绩全部修改一遍，只需要做两个标记：

在第 2 名学生的位置标记 $+3$ ，表示从这里开始加分。
在第 5 名学生的位置标记 $-3$ ，表示从这里开始取消加分。

之后从左往右累计这些标记，就能知道每个人应该增加多少分。

假设原来的 5 个数都是 0。

位置	2	3	4	5
原数组	0	0	0	0
差分标记	+3	0	0	-3
累加结果	3	3	3	0

可以看到，第 2、3、4 个位置都增加了 3，其余位置保持不变。

因此，如果需要把区间 $[l,r]$ 中的数全部增加 $c$ ，只需要：

$\boxed{d[l]+=c}$

$\boxed{d[r+1]-=c}$

注意：一定是 $r+1$ ，而不是 $r$ ！

因为第 $r$ 个位置仍然需要增加 $c$ ，到了第 $r+1$ 个位置才应该取消。

3. 如何构造差分数组？

如果原数组本来就有数值，就需要先构造差分数组。

差分数组记录的是当前位置与前一个位置相差多少。

例如：

$a=[2,5,4,7]$

对应的差分数组为：

$d=[2,3,-1,3]$

因为：

第 1 个位置： $2$
第 2 个位置： $5-2=3$
第 3 个位置： $4-5=-1$
第 4 个位置： $7-4=3$

因此：

$\boxed{d[i]=a[i]-a[i-1]}$

其中，规定 $a[0]=0$ 。

4. 如何还原原数组？

差分数组只记录相邻位置之间的变化，并不是最终的数值。

想恢复原数组，只需要从左往右不断累加。

例如：

$d=[2,3,-1,3]$

还原的过程：

$a[1]=2$

$a[2]=2+3=5$

$a[3]=2+3-1=4$

$a[4]=2+3-1+3=7$

因此：

$\boxed{a[i]=a[i-1]+d[i]}$

是不是很熟悉？

差分数组通过前缀和，就能还原原数组。

这就是前缀和与差分之间最重要的联系。

5. 差分代码

// 第一步：构造差分数组
for(int i = 1; i <= n; i++) {
    d[i] = a[i] - a[i - 1];
}

// 第二步：多次区间修改
while(q--) {
    int l, r;
    long long c;
    cin >> l >> r >> c;

    d[l] += c;
    d[r + 1] -= c;
}

// 第三步：还原最终数组
for(int i = 1; i <= n; i++) {
    a[i] = a[i - 1] + d[i];
}

注意：

数组从 1 开始， $a[0]=0$ 。
差分数组需要多开一个位置，保证 $d[n+1]$ 不会越界。
区间修改时不需要直接修改原数组。
所有区间修改完成后，再利用前缀和还原结果。

6. 课堂练习

第 3 题：A83456 最多涂色次数

每次给一段区间涂色，求被涂色次数最多的位置的涂色次数。

思路：每个区间都在起点增加 1，在终点的下一个位置减少 1。最后求前缀和，并找出最大值。

注意题目中的坐标起点，避免下标错误。

第 4 题：A83455 考试补分

对已有的成绩数组进行多次区间加分，求最后的最低成绩。

思路：

根据原始成绩构造差分数组。
使用差分进行多次区间修改。
还原最终成绩数组。
遍历数组，找到最小值。

四、前缀和与差分的区别

对比	前缀和	差分
主要作用	快速查询区间和	快速修改整个区间
预处理	不断累加	与前一个数相减
核心操作	两个前缀和相减	修改区间的两个边界
后续处理	直接回答查询	最后通过前缀和还原
常见题型	多次区间求和	多次区间加减