arrays - 範囲内の配列要素に特定の値を追加するための高速アルゴリズム?

Question

範囲更新の質問で、範囲内の配列要素に値を追加したいと考えています。配列 (または何らかのデータ構造) がソートされていると想定できます。

単純なアルゴリズムでは、開始要素から終了要素までループし、各要素に値 v を追加します。

ただし、範囲が最初の要素から最後の要素までの場合、最悪の場合は O(n) 時間かかります。これを行うより速い方法はありますか？セグメントツリーを使用する必要がありますか?

Answer 1

配列がソートされている場合は、範囲に属する単一の要素をすばやく検索できます (たとえば、バイナリ検索を使用)。その後、エントリ ポイントの前後の要素に増分値を追加します。

たとえば、配列に int を含めることができます。したがって、コードは次のようになります。

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 2

配列が実際に ac スタイルの配列 (必ずしもソートされているとは限りません) であり、構造 O(n) にその順序が暗黙的に含まれているツリーのようなデータ構造ではない場合は、取得できる最高のものです。

他のデータ構造 (さまざまな種類のツリー) があり、検索を高速化できます。ただし、並べ替えられていない配列をこれらの構造の 1 つに変換すると、常に O(n) よりも悪くなります。