arrays - 将特定值添加到范围内的数组元素的快速算法？

Question

在范围更新问题中，我想向范围内的数组元素添加一个值。可以假定数组(或某些数据结构)已排序。

一个简单的算法是遍历起始元素到结束元素，并为每个元素添加一个值 v。

但是在最坏的情况下，当范围是从第一个元素到最后一个元素时，这需要 O(n) 的时间。有没有更快的方法来做到这一点？我应该使用线段树来做吗？

Answer 1

如果速度很重要并且您只在封闭范围内操作并添加每个时间常数值，您可以创建“修改队列”，您可以在其中放置修改序列，由 (starting index, ending index, delta)，保持数组本身不变。实际处理可能会在事件最少的时候执行。

这将使修改在保证的 O(1) 内运行，但随机读取成本将增加到 O(K)，其中 K 是队列的大小(后续刷新之间的平均修改次数)。如果数组很大且范围很宽，但修改发生的频率不高且必须快速返回，则这种方法可能会获胜。