前缀和与差分

定义

前缀和：数组a[N], 其前缀和s[N]定义为s[i] = a[0] + a[1] + ... + a[i]

差分：有一个数组s[N], 创建一个数组b[N], 令b[0] + b[1] + ... + b[i] = s[i]

可以看到前缀和与差分是一对逆运算。

即上述的a[N] 和 b[N]可以等价，b[N]的前缀和是s[N], s[N]的差分为b[N], 同上a[N]

功能

• 前缀和：可以很快（O(1)）的得到原数组某一段之后：求a[l] - a[r]这一段的和，利用s[r] - s[l - 1]

• 差分：可以在O(1)时间内，使得数组某一段一起增加一个数c：即 a[l] = a[l] + c .. a[r] = a[r] + c

• 同理可以作用在二维的前缀和矩阵、差分矩阵，此时需要作图辅助进行构造