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

Question

在范围更新问题中，我想向范围内的数组元素添加一个值。可以假设数组（或一些数据结构）是排序的。

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

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

Answer 1

如果数组真的是一个 c 风格的数组（不一定是排序的）而不是一个树状的数据结构，它已经在其结构中隐含地包含它的顺序 O(n) 是你能得到的最好的。

还有其他数据结构（各种类型的树，可以加快查找速度。但是，将未排序的数组转换为其中一种结构总是比 O(n) 更糟糕。

Answer 2

如果你的数组是排序的，那么你可以快速搜索（例如，使用二进制搜索）属于你的范围的任何单个元素。此后，将增量值添加到入口点前后的元素。

例如，让数组包含整数。所以代码将是这样的：

int *p;
// try to fill array from begin to element range_max
if(your_array[0] >= range_min) {
  for(p = your_array; p < your_array + elems_qty; p++)
    if(*p <= range_max)
      *p += delta;
    else 
      break;
  return; // head of array filled
}

// try to fill array from end to element range_min
if(your_array[elms_qty - 1] <= range_max) {
  for(p = your_array + elms_qty - 1; p >= your_array; p--)
    if(*p >= range_min)
      *p += delta;
    else 
      break;
  return; // tail of array filled
}

// There is range somewhere inside array

int avg_element = (range_min + range_max) / 2;

int *avg_ptr = bsearch(&avg_element, your_array, elems_qty, sizeof(int), int_comparator);

for(p = avg_ptr; *p >= range_min; p--)
  *p += delta;

for(p = avg_ptr; *p <= range_max; p++)
  *p += delta;

Answer 3

如果速度很重要并且您仅在封闭范围内操作并添加每个时间常数值，则可以创建 "modification queue" 放置修改序列，由 (starting index, ending index, delta) 定义，保持数组本身不变。实际处理可能至少在 activity.

时执行

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

Answer 4

您可以使用 Fenwick Tree。它比线段树更容易实现。（它被称为树，但它实际上是作为数组实现的，就像二叉堆一样）。

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

Fast algorithm for adding a specific value to array elements in a range?

arrays

algorithm

segment-tree