前缀和与差分数组

类似于数学中的求导和积分，差分可以看成前缀和的逆运算。

前缀和

假设有这么一个数组 a，它有 n 个元素：a[1], a[2], ..., a[n]

为了在 $O(1)$ 时间复杂度内求出数组 a 的区间和，需要构造一个前缀和数组 b。

b[1] = a[1]                            = a[1]
b[2] = a[1] + a[2]                     = a[2] + b[1]
b[3] = a[1] + a[2] + a[3]              = a[3] + b[2]
......
b[n] = a[1] + a[2] + a[3] + ... + a[n] = a[n-1] + b[n-1]

假如现在要求 a[2] 到 a[7] 之间的和，b[7] - b[1] 就是结果。

假如现在要求 a[r] 到 a[l] 之间的和，b[r] - b[l-1] 就是结果。

提示

• b[i] 数组代表着 a[1] 到 a[i] 的和
• b[7] 包括 a[7]，b[1] 不包括 a[2]
• b[7] - b[1] 即 a[2] 到 a[7] 之间的和

ACWING：前缀和

差分

差分可以看成前缀和的逆运算。

在刚刚前缀和中，b 是 a 数组的前缀和，那么 a 就是 b 数组的差分。

a[1] = b[1]
a[2] = b[2] - b[1]
a[3] = b[3] - b[2]
a[4] = b[4] - b[3]
......
a[n] = b[n] - b[n-1]

这样就会通过前缀和导出一个性质：

如果 a[1] + 1，在前缀和数组里 b[1] 以后的元素全部都会 + 1。

为了在 $O(1)$ 时间复杂度，给数组 b[2] 到 b[7] 之间的所有元素 + 1

只需要 a[2] + 1 和 a[8] - 1。

提示

• a[2] 后面的数包括：b[2] 到 b[n]
• a[8] 后面的数包括：b[8] 到 b[n]（不包括 b[7]）

ACWING：前缀和