差分数组

以一个例子来了解差分数组

考虑数组arr=[1,3,7,4,8,9,10];arr=[1, 3, 7, 4, 8, 9, 10]; 现在将它们相邻两两作差，即右边减左边，得到数组[2,4,−3,4,1,1],[2,4,-3,4,1,1], 如果在原数组前面加上一个00，或者说在差分数组中补上arr[0]arr[0], 得到差分数组diff=[1,2,4,−3,4,1,1],diff=[1,2,4,-3,4,1,1], 这个数组从左往右求和即可得到原数组，有点类似积分和求导的关系。

那这么一个数组有什么用呢？现在对原数组的arr[1] 到 arr[5]arr[1]~到~arr[5]进行逐元素加1010操作, 得到数组arr′=[1,13,17,14,18,19,10],arr'=[1,13,17,14,18,19,10], 它的差分数组为diff′=[1,12,4,−3,4,1,−9]diff'=[1,12,4,-3,4,1,-9]，可以发现只有diff[1]diff[1]和diff[6]diff[6]发生了变化，分别+10+10和−10-10。

不难证明，因为连续操作数组值时，序列内部差值不会变化，只有边界会被影响。

因此差分数组可以把原来对数组O(n)O(n)的操作映射到差分数组上O(1)O(1)的操作。