简单说就是多次对数组任意区间内的数据进行加减,最后要能得出数组里任意位置的值.¶
如果区间范围比较大.暴力遍历效率太低,不可能每次修改都去遍历整个区间.
可以总结出从d推出a中任意值的公式:
又可以发现一个性质,如果给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. 这样就实现了只修改两个值就修改了任意区间内所有的元素. 适用于频繁修改区间并少量统计.
假设有n = i - 4 那么n到i之间的和就等于所有的和减去从第五行开始的和,即d前四行的和.是个较简单的计算.
差分数组在类似的区间统计问题中可实现O(1)复杂度的修改和O(n)复杂度的单值或区间和的查询.
简单说就是多次对数组任意区间内的数据进行加减,最后要能得出数组里任意位置的值.