差分

前缀和与差分概念 有一个数组为 [1, 2, 3, 4, 5] , 他的前缀和数组就是 [1, 3, 6, 10, 15] 公式为 sum[i] = a[i] + sum[i - 1]; 有一个数组为 [1, 3, 6, 10, 15] , 他的差分数组为 [1, 2, 3, 4, 5] , 公式为 a[i] = sum[i] - sum[i - 1]; 也就是说, 我们在对差分数组中的一个位置 加上一个数时, 如果不在后面减去相同的数值, 那么在对差分数组求前缀和后, 前缀和数组的每...