12

Fenwick Tree（またはBinary Indexed Tree）を次のように変更できるかどうか疑問に思いました。

1）範囲内のすべての要素の周波数を特定の量だけ増加させます

2）単一要素の頻度を照会します。

これは、更新が単一の要素で実行され、クエリが範囲全体で実行される従来のフェンウィックツリーとは対照的です（逆フェンウィックツリーのようなものです）。

4

1 に答える 1

20

もちろん！

フェニックツリーを使用すると、O（log n）でこれらの操作を実行できます。

update(x, delta)   => increases value at index x by delta
query(x)           => returns sum of values at indices 0,1,2,...,x

C++でのFenwickツリーの簡単な実装は次のとおりです。

int F[MAX];

void update( int x, int delta ) {
  for( ++x; x < MAX; x += x&-x ) F[x] += delta;
}

int query( int x ) {
  int sum = 0;
  for( ++x; x > 0; x -= x&-x ) sum += F[x];
  return sum;
}

ここで、フェンウィックツリーの内部を忘れて、問題に焦点を合わせます。フェニック木を使用するときは、文字通り周波数の配列を格納し、どういうわけか魔法のように両方の操作をO（log n）で実行することを想像してみてください。関数の更新は単一の要素の頻度を変更し、クエリは最初のx要素の頻度の合計を返します。

したがって、「従来の」問題では、次の操作が行われました。

void incFreqAt( int index ) {
  update( index, 1 );
}

int getFreqAt( int index ) {
  return query( index ) - query( index-1 );
}

ここで、各単一要素の頻度を保存する代わりに、隣接する要素の頻度間の差を保存しましょう。

これらは新しい操作です：

void incFreqFromTo( int a, int b, int delta ) {
  update( a, delta );
  update( b+1, -delta );
}

int getFreqAt( int index ) {
  return query( index );
}

範囲[a..b]の周波数をインクリメントするときは、インデックスaで差をインクリメントし、インデックスb+1で差をデクリメントします。これは、次のようにも言います。範囲[a..infinity]のすべての周波数をインクリメントし、範囲[b +1..infinity]のすべての周波数をデクリメントします。

インデックスxの要素の頻度を取得するには、範囲[0..x]の頻度のすべての差を合計するだけです。

于 2012-04-10T23:00:13.233 に答える