バイナリインデックスツリーには、他のデータ構造と比較して、研究する理論がほとんどないか、比較的ありません。それが簡潔に教えられている唯一の場所は、トップコーダーのチュートリアルです。チュートリアルはすべての説明で完了していますが、そのような木の背後にある直感が何であるか理解できません。そして、それが正しいことを証明する方法は？
証明は説明するのが複雑だと思います。では、BITを使用する場合、どのようなアプローチに従いますか？
質問する
12627 次
1 に答える
78
@templatetypedef によるこの回答は、バイナリ インデックス ツリーの直感と証明について非常に明確に説明されていることがわかりました。
直感的に、バイナリ インデックス ツリーは、それ自体が標準的な配列表現の最適化であるバイナリ ツリーの圧縮された表現と考えることができます。この答えは、1つの可能な派生になります。
たとえば、合計 7 つの異なる要素の累積度数を保存するとします。数値が分配される 7 つのバケットを書き出すことから始めることができます。
[ ] [ ] [ ] [ ] [ ] [ ] [ ]
1 2 3 4 5 6 7
ここで、累積度数が次のようになるとします。
[ 5 ] [ 6 ] [14 ] [25 ] [77 ] [105] [105]
1 2 3 4 5 6 7
このバージョンの配列を使用すると、その場所に格納されている数値の値を増やし、その後に続くすべての頻度を増やすことで、任意の要素の累積頻度を増やすことができます。たとえば、3 の累積度数を 7 ずつ増やすには、次のように、配列内の位置 3 以降の各要素に 7 を追加します。
[ 5 ] [ 6 ] [21 ] [32 ] [84 ] [112] [112]
1 2 3 4 5 6 7
これに関する問題は、これを行うのに O(n) 時間がかかることであり、n が大きい場合はかなり遅くなります。
この操作を改善するために考えられる 1 つの方法は、バケットに保存するものを変更することです。特定の時点までの累積頻度を保存するのではなく、現在の頻度が以前のバケットと比較して増加した量を保存することを考えることができます。たとえば、この場合、上記のバケットを次のように書き換えます。
Before:
[ 5 ] [ 6 ] [21 ] [32 ] [84 ] [112] [112]
1 2 3 4 5 6 7
After:
[ +5] [ +1] [+15] [+11] [+52] [+28] [ +0]
1 2 3 4 5 6 7
これで、バケットに適切な量を追加するだけで、時間 O(1) でバケット内の頻度を増やすことができます。ただし、すべての小さなバケットの値を合計してバケットの合計を再計算する必要があるため、ルックアップの総コストは O(n) になります。
ここからバイナリ インデックス ツリーに到達するために必要な最初の主要な洞察は次のとおりです。順番のポイント？それができれば、これらの事前計算された合計の正しい組み合わせを合計するだけで、ある時点での累積合計を計算できます。
これを行う 1 つの方法は、表現をバケットの配列からノードのバイナリ ツリーに変更することです。各ノードには、その特定のノードの左側にあるすべてのノードの累積合計を表す値で注釈が付けられます。たとえば、これらのノードから次のバイナリ ツリーを構築するとします。
4
/ \
2 6
/ \ / \
1 3 5 7
これで、そのノードとその左側のサブツリーを含むすべての値の累積合計を格納することで、各ノードを拡張できます。たとえば、値が与えられた場合、次を保存します。
Before:
[ +5] [ +1] [+15] [+11] [+52] [+28] [ +0]
1 2 3 4 5 6 7
After:
4
[+32]
/ \
2 6
[ +6] [+80]
/ \ / \
1 3 5 7
[ +5] [+15] [+52] [ +0]
このツリー構造を考えると、あるポイントまでの累積合計を簡単に決定できます。アイデアは次のとおりです。最初は 0 のカウンターを維持し、問題のノードが見つかるまで通常のバイナリ検索を実行します。その際、次のことも行います。右に移動するたびに、現在の値もカウンターに追加します。
たとえば、3 の合計を調べたいとします。そのためには、次のようにします。
- ルートから開始します (4)。カウンターは0です。
- 左のノード (2) に移動します。カウンターは0です。
- ノード (3) に右に移動します。カウンターは 0 + 6 = 6 です。
- ノード (3) を見つけます。カウンターは 6 + 15 = 21 です。
このプロセスを逆に実行することも想像できます。特定のノードから始めて、カウンターをそのノードの値に初期化し、ツリーをルートまでたどります。右の子リンクを上にたどるときはいつでも、到達したノードで値を追加します。たとえば、3 の度数を見つけるには、次のようにします。
- ノード (3) から開始します。カウンターは15。
- 上のノード (2) に移動します。カウンターは 15 + 6 = 21 です。
- ノード (1) まで上に移動します。カウンターは21。
ノードの頻度 (および暗黙のうちに、そのノードの後に続くすべてのノードの頻度) を増やすには、左側のサブツリーにそのノードを含むツリー内のノードのセットを更新する必要があります。これを行うには、次のことを行います。そのノードの頻度を増やしてから、ツリーのルートまで歩き始めます。左の子として表示されるリンクをたどるたびに、現在の値を追加して、遭遇するノードの頻度を増やします。
たとえば、ノード 1 の頻度を 5 ずつ増やすには、次のようにします。
4
[+32]
/ \
2 6
[ +6] [+80]
/ \ / \
> 1 3 5 7
[ +5] [+15] [+52] [ +0]
ノード 1 から始めて、周波数を 5 ずつ増やして取得します。
4
[+32]
/ \
2 6
[ +6] [+80]
/ \ / \
> 1 3 5 7
[+10] [+15] [+52] [ +0]
次に、その親に移動します。
4
[+32]
/ \
> 2 6
[ +6] [+80]
/ \ / \
1 3 5 7
[+10] [+15] [+52] [ +0]
左の子リンクを上にたどったので、このノードの頻度も増やします。
4
[+32]
/ \
> 2 6
[+11] [+80]
/ \ / \
1 3 5 7
[+10] [+15] [+52] [ +0]
次に、その親に移動します。
> 4
[+32]
/ \
2 6
[+11] [+80]
/ \ / \
1 3 5 7
[+10] [+15] [+52] [ +0]
これは左の子リンクだったので、このノードもインクリメントします。
4
[+37]
/ \
2 6
[+11] [+80]
/ \ / \
1 3 5 7
[+10] [+15] [+52] [ +0]
これで完了です。
最後のステップは、これを 2 進インデックス ツリーに変換することです。ここで、2 進数を使って楽しいことを行うことができます。このツリーの各バケット インデックスをバイナリで書き直してみましょう。
100
[+37]
/ \
010 110
[+11] [+80]
/ \ / \
001 011 101 111
[+10] [+15] [+52] [ +0]
ここで、非常にクールな観察を行うことができます。これらの 2 進数のいずれかを取得し、数値に設定された最後の 1 を見つけて、そのビットを削除し、その後に続くすべてのビットを削除します。これで、次のものが残ります。
(empty)
[+37]
/ \
0 1
[+11] [+80]
/ \ / \
00 01 10 11
[+10] [+15] [+52] [ +0]
ここに、非常に優れた観察があります。0 を「左」を意味し、1 を「右」を意味する場合、各数値の残りのビットは、ルートから開始してその数値まで進む方法を正確に説明します。たとえば、ノード 5 のバイナリ パターンは 101 です。最後の 1 は最後のビットなので、それを削除して 10 を取得します。実際、ルートから開始して右 (1) に移動し、次に左 (0) に移動すると、終了します。ノード5でアップ！
これが重要な理由は、ルックアップと更新の操作が、ノードからルートまでのアクセス パスと、左または右の子リンクをたどるかどうかに依存するためです。たとえば、ルックアップ中は、たどる左側のリンクだけを気にします。更新中は、たどる正しいリンクだけを気にします。このバイナリ インデックス ツリーは、インデックス内のビットを使用するだけで、これらすべてを非常に効率的に実行します。
重要なトリックは、この完全なバイナリ ツリーの次のプロパティです。
ノード n が与えられると、ルートに戻るアクセス パス上の次のノードは、n のバイナリ表現を取得し、最後の 1 を削除することによって得られます。
たとえば、ノード 7 のアクセス パス (111) を見てみましょう。ルートへのアクセス パス上のノードのうち、右のポインターを上にたどるノードは次のとおりです。
- ノード 7: 111
- ノード 6: 110
- ノード 4: 100
これらはすべて正しいリンクです。011 であるノード 3 のアクセス パスを取得し、右側にあるノードを見ると、次のようになります。
- ノード 3: 011
- ノード 2: 010
- (ノード 4: 100、左のリンクをたどる)
これは、次のように、ノードまでの累積合計を非常に効率的に計算できることを意味します。
- ノード n をバイナリで書き出します。
- カウンターを 0 に設定します。
- n ≠ 0 の間、次を繰り返します。
- ノード n の値を追加します。
- n から左端の 1 ビットを削除します。
同様に、更新ステップを実行する方法について考えてみましょう。これを行うには、ルートまでアクセス パスをたどって、左のリンクを上にたどったすべてのノードを更新します。これを行うには、基本的に上記のアルゴリズムを実行しますが、すべての 1 を 0 に、0 を 1 に切り替えます。
バイナリ インデックス ツリーの最後のステップは、このビット単位のトリックにより、ツリーを明示的に格納する必要さえなくなったことに注意することです。すべてのノードを長さ n の配列に格納し、ビット単位の調整手法を使用して暗黙的にツリーをナビゲートできます。実際、ビット単位のインデックス付きツリーはまさにそれを行います。ノードを配列に格納し、これらのビット単位のトリックを使用して、このツリーを上方向に効率的にシミュレートします。
お役に立てれば！
于 2013-03-16T02:35:55.367 に答える