前缀和 与 差分

前缀和 与 差分"/>

前缀和 与 差分

前缀和

对于一个给定的数列 A A A，它的前缀和数列 S S S 是通过递推能求出的基本信息之一：
S [ i ] = ∑ j = 1 i A [ j ] S[i] = \sum_{j=1}^{i} A[j] S[i]=j=1∑i​A[j]
一个部分和，即数列 A A A 某个下标区间内的数的和，可表示为前缀和相减的形式：
s u m ( l , r ) = ∑ i = l r A [ i ] = S [ r ] − S [ l − 1 ] sum(l,r) = \sum_{i=l}^rA[i] = S[r] - S[l - 1] sum(l,r)=i=l∑r​A[i]=S[r]−S[l−1]
在二维数组（矩阵）中，可类似地求出二维前缀和，进一步计算出二维部分和。

二维数组前缀和应用：AcWing99. 激光炸弹

差分

对于一个给定的数列 A A A，它的差分数列 B B B 定义为：
B [ 1 ] = A [ 1 ] ， B [ i ] = A [ i ] − A [ i − 1 ] ( 2 ≤ i ≤ n ) B[1] = A[1]，B[i] = A[i] - A[i-1] \ \ \ \ \ \ (2 \le i \le n) B[1]=A[1]，B[i]=A[i]−A[i−1]      (2≤i≤n)

容易发现，“前缀和” 与 “差分” 是一对互逆运算，差分序列 B B B 的前缀和序列就是原序列 A A A，前缀和序列 S S S 的差分序列也是原序列 A A A。

把序列 A A A 的区间 [ l , r ] [l,r] [l,r] 加 d d d（即把 A l , A l + 1 , . . . , A r A_l, A_{l+1}, ... , A_r Al​,Al+1​,...,Ar​ 都加上 d d d），其差分序列 B B B 的变化为 B l B_l Bl​ 加 d d d， B r + 1 B_{r+1} Br+1​ 减 d d d，其他位置不变。 这有助于在很多题目中，把原序列上的 “区间操作” 转化为差分序列上的 “单点操作” 进行计算，降低求解难度。

差分应用：AcWing100.增减序列