前缀和数组

前缀和数组： 新建一个数组B, 数组第i项是数组A第0个到i-1个元素的累加和。

B[i] = sum(A[0,1..i])

差分数组

差分数组的概念对应的是前缀和数组， 对于数组[1,2,3,4], 其差分数组为[1,1,0,2], 差分数组的第i个数即为原数组的第i-1个元素和第i个元素的差值, 也就是说我们对差分数组求前缀和即可得到原数组。