差分数组的应用#

问题#

题目见 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)复杂度的单值或区间和的查询。