前缀和和差分

前缀和和差分

前缀和

差分

一个数组 a[n] = b[1] + b[2] + … + b[n]
数组b 即为 a的差分数组 （a为b的前缀和数组）

当 b[3] += c 时意味着 从a[3] 到 a[n] 都会加上c

如果想要对原数组 a 中的某段区间[l,r]都加上一个数
操作分为两步：

1. 对其差分数组进行 b[l] += c; b[r+1] -= c;

2. 再对差分数组求和即可得到想要的数组

给定两个序列，要求将其中一个序列变成另一个序列，我们都可以将其转化到差分数组上，让两个序列的差分数组相同 A ——> B 相当于从 A-B ——> 0