前缀和，差分

主播刚开始学算法时，觉得差分和前缀和这两个东西名字很吓人，非常的难写。其实它们一点也不吓人。你可以先记住一句话：

前缀和=快速求一段区间的和。

差分=快速对一段区间整体加减。

如果把数组看成一排数字，那么：

• 前缀和解决的是：这一段数字加起来等于多少。
• 差分解决的是：这一整段数字都加上一个数，怎么做的更快。

一.学前缀和和差分的作用

先看一个很常见的问题。

有一个数组：

如果我要问你：

• 第2个到第4个数和是多少？
• 第1个到第5个数和是多少？
• 第3个到第5个数和是多少？

你当然可以每次一遍遍的加，但如果题目的数据范围很大呢？

这时候你如果还是每次都重新加，速度就会很慢。

所以我们就需要一种方法，能让求一段区间和变得特别快，这就是前缀和。

同理，如果题目不是问区间和，而是让你：

• 把第2个到第4个数都加3。
• 把第1个到第5个数都减2。
• 把第3个到第6个数都加10。

如果每次都一个个改，也会很慢。

所以我们还需要一种方法，能让区间整体修改变得很快，这就是差分。

二、前缀和是什么

（1）前缀和的定义

前缀和，顾名思义，就是前面所有数的和。

比如数组：

a=[1，2，3，4，5]

我们定义一个新数组s，其中：

• s[1]表示前1个数的和。
• s[2]表示前2个数的和。
• s[3]表示前3个数的和。
• ……

那么：

s[1]=1

s[2]=1+2=3

s[3]=1+2+3=6

s[4]=1+2+3+4=10

s[5]=1+2+3+4+5=15

所以前缀和数组就是：

s=[0,1,3,6,10,15]

前缀和数组定义时，每次多放一位0是为了方便计算。

（2）前缀和怎么求

公式很简单：

意思是：

前i个数的和=前i-1个数的和+第i个数。

（3）前缀和最重要的作用

快速求区间和

比如我们要求第l个到第r个数的和。

正常做法是：

前缀和的做法是：

（4）为什么是

因为：

• a[r]是前r个数的和。
• a[l-1]是前l-1个数的和。

把前面那一段减掉，剩下的就是l到r的和。

举一个例子

还是a=[1，2，3，4，5]

前缀和：

s=[0,1,3,6,10,15]

求第2到第4个数的和：
s[4]-s[1]=10-1=9

而原数组第2到第4个数是：

2+3+4=9

两个的结果完全一样。

三、前缀和模板

（1）一维前缀和模板

n = len(a)
s = [0] * (n + 1)

for i in range(1, n + 1):
s[i] = s[i – 1] + a[i – 1]

四、差分是什么

如果说前缀和是快速求和，那么差分就是快速修改。

（1）差分的核心想法

假设现在有数组：

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

我想把第2到第4个数都加3。

改完后直接变成：

a=[1,5,6,7,5]

普通做法是：

• 第2个加3
• 第3个加3
• 第4个加3

这样一个个改。

但差分的思想是：
不直接改整个区间，只在区间的开头和结尾做标记。

（2）差分数组的定义

差分数组b满足：

b[i]=a[i]-a[i-1]

也就是说，差分数组记录的是当前数和前一个数差了多少。

比如：

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

那么差分数组可以是：

b[1]=1

b[2]=2-1

b[3]=3-2

b[4]=4-3

b[5]=5-4

所以：

b=[1,1,1,1,1]

（3）差分怎么进行区间修改

如果要把区间[l，r]都加上K，只需要：
b[l]+=k

b[r+1]-=k

（4）为什么这样做是对的

因为：

• 从l开始，后面的数都应该多k。
• 从r+1以后，这个多出来的k就应该停在。

所以：

在l位置加上k，表示从这里开始整体增加。

在r+1位置减去k，表示从这里后面停止增加。

这就像在一个区间的左右两打标记一样。

（5）差分数组

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

b=[1,1,1,1,1]

现在给区间[2,4]加上3。

那么只需要：

b[2]+=3

b[5]-=3

得到：
b=[1,4,1,1,-2]

然后再把差分数组还原成原数组：

• 第1个数：1
• 第2个数：1+4=5
• 第三个数：5+1=6
• 第四个数：6+1=7
• 第五个数：7+（-2）=5

得到：

[1,5,6,7,5]

正好就是我们想要的结果。

五、差分模板

（1）建立差分数组

import sys
from collections import deque,defaultdict
input=sys.stdin.readline
n=len(a)
b=[0]*(n+2)
b[1]=a[0]
for i in range(2,n+1):
b[i]=a[i-1]-a[i-2]

（2）区间修改

把[l，r]全部加上k:

b[l]+=k
b[r+1]-=k

（3）还原原数组

for i in range(1,n+1):
b[i]+=b[i-1]

此时b[i]就已经变成修改后的原数组了。

六、前缀和和差分的关系

这两个东西其实是反过来的关系。

前缀和

是把原数组不断累加：

差分

是看原数组相邻两项的差值：

所以可以理解为：

前缀和：往前累加。

差分：看变化量。

七、什么时候用前缀和？什么时候用差分？

这个非常的重要。

用前缀和的情况

当题目经常问你：

• 区间和
• 一段连续数字的总和
• 多次查询某段区间的和

这时候优先想到：前缀和。

用差分的情况

当题目经常让你：

• 给一整段区间同时加一个数。
• 多次进行区间修改。
• 最后再求整个数组结果

这时候优先想到：差分。

一句话总结

多次查询区间和，用前缀和。

多次修改整个区间，用差分。

八、常见的错误点

（1）下标混乱

（2）忘记把数组开大一个位置

（3）前缀和公式写错