Fenwick Tree(またはBinary Indexed Tree)を次のように変更できるかどうか疑問に思いました。
1)範囲内のすべての要素の周波数を特定の量だけ増加させます
2)単一要素の頻度を照会します。
これは、更新が単一の要素で実行され、クエリが範囲全体で実行される従来のフェンウィックツリーとは対照的です(逆フェンウィックツリーのようなものです)。
Fenwick Tree(またはBinary Indexed Tree)を次のように変更できるかどうか疑問に思いました。
1)範囲内のすべての要素の周波数を特定の量だけ増加させます
2)単一要素の頻度を照会します。
これは、更新が単一の要素で実行され、クエリが範囲全体で実行される従来のフェンウィックツリーとは対照的です(逆フェンウィックツリーのようなものです)。
もちろん!
フェニックツリーを使用すると、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]の頻度のすべての差を合計するだけです。