差分数组的应用

问题

题目见 https://leetcode-cn.com/problems/corporate-flight-bookings/

简单说就是多次对数组任意区间内的数据进行加减，最后要能得出数组里任意位置的值。

• 比如初始数据[0, 0, 0, 0]
  对[1, 4]加2，得到[2, 2, 2, 2]。
  再对[2,3]减1，得到[2, 1, 1, 2]。

• 如果区间范围比较大。暴力遍历效率太低，不可能每次修改都去遍历整个区间。

• 可做一个差分数组。
  例如对于包含实际值的数组a:
  1 3 99  50  12 20
  可以有一个差分数组d:
  1 2 96 -49 -38 8

  限定d的每个值是a中相对的元素减去前一个元素的值:
  d[i] = a[i] - a[i - 1] d[0] = a[0]

  可以总结出从d推出a中任意值的公式：

  a[i] = a[i - 1] + d[i]
       = a[i - 2] + d[i - 1] + d[i]
       = a[i - 3] + d[i - 2] + d[i - 1] + d[i]
       = a[0] + ... + d[i]
       = d[0] + ... + d[i]
  

  即a[i]为d[0]到d[i]的和。

• 又可以发现一个性质，如果给d[i]加n，那么a[i]及之后的值都会加n，之前的不受影响。

  可以利用这个性质实现区间内所有值快速加减。

  例如给d[i]加n，这样a[i]开始的元素都加n。
  再给d[i + 3]减n，这样a[i + 3]开始的元素都减n，抵消之前加的n。
  结果就是区间内的a[i],a[i + 1],a[i + 2]三个值都加了n。
  这样就实现了只修改两个值就修改了任意区间内所有的元素。
  适用于频繁修改区间并少量统计。

• 另外也可以统计区间内的和

  a前i项的和：

  + d[0] + ... + d[i - 5] + d[i - 4] + d[i - 3] + d[i - 2] + d[i - 1] + d[i]
  + d[0] + ... + d[i - 5] + d[i - 4] + d[i - 3] + d[i - 2] + d[i - 1]
  + d[0] + ... + d[i - 5] + d[i - 4] + d[i - 3] + d[i - 2]
  + d[0] + ... + d[i - 5] + d[i - 4] + d[i - 3]
  + d[0] + ... + d[i - 5] + d[i - 4]
  + d[0] + ... + d[i - 5]
  + d[0]
  

  假设有n = i - 4
  那么n到i之间的和就等于所有的和减去从第五行开始的和，即d前四行的和。是个较简单的计算。

---

总结

差分数组在类似的区间统计问题中可实现O(1)复杂度的修改和O(n)复杂度的单值或区间和的查询。