什么是差分数组（difference array）
date
Jun 10, 2021
slug
什么是差分数组（difference array）
status
Published
tags
LeetCode
summary
有一个数组
arr，我们需要频繁对arr中的子数组进行更新，比如为子数组的元素+1，容易想到的办法是每次都用一个循环进行更新，但这其实是个时间复杂度O(N)的操作，效率是不高的。有没有什么办法可以高效的进行更新（比如O(1)的时间复杂度）？type
Post
遇到的问题
有一个数组
arr，我们需要频繁对arr中的子数组进行更新，比如为子数组的元素+1，容易想到的办法是每次都用一个循环进行更新，但这其实是个时间复杂度O(N)的操作，效率是不高的。有没有什么办法可以高效的进行更新（比如O(1)的时间复杂度）？什么是差分数组？
如果我们有个数组
arr如果有另外一个数组
diff，且有diff[i] = arr[i] - arr[i - 1]、diff[0] = arr[0]，即diff中每个元素的值是arr中对应元素和前一个元素的差值，这个数组就是差分数组差分数组有什么用？
回到刚才的问题，如果我们要给
[1,4]范围内的子数组元素的值+3，除了用循环之外，还能怎么做？我们把增加后的结果写出来看下
如果我们关注
diff，会发现只有diff[1]和diff[4]变化了，diff[2]和diff[3]没变化，因为范围内都+3了，所以差值就没有改变，这样我们就利用差分数组把一个O(N)的操作转化为一个O(1)的操作。在实际使用中，我们不用去更新原数组，同一份数据，使用差分数组表示之后，就可以把这种范围的更新操作时间复杂度降为O(1)。差分数组的问题是，不像普通数组那样有随机访问的能力，比如要知道修改后第
1个元素的值，我们只能通过arr[1 - 1] + diff[1]来算。这是一个O(N)的操作。