前缀和

1. 作用：O(1)的时间复杂度求出一段区间的和

a[1], a[2], ... a[n]
s[i] 前i个数的和
s[i] = s[i - 1] + a[i]
求[l, r]区间的和 = s[r] - s[l - 1]

差分

类似于数学中的求导和积分，差分可以看成前缀和的逆运算
举例：
a[1], a[2], … a[n]
b[1], b[2], … b[n]
其中
b[1] = a[1],
b[2] = a[2] - a[1]
b[3] = a[3] - a[2]
…
b[n] = a[n] - a[n - 1]
a数组是b数组的前缀和数组，b数组就是a数组的差分数组
差分数组的作用：O(1)的时间复杂度对a数组的一段区间[l,r]做加上一个数c
b[i] + c意味着a[i]至a[n]加上了一个数c
同理 b[i] - c意味着a[i]至a[n]减去了一个数c