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

Question

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

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

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

Answer 1

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

Answer 2

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

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

Answer 3

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

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

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 4

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

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