3

インターネットでバイナリインデックスツリー（別名フェニックツリー）の2〜3のチュートリアルを読みましたが、実際に何が行われ、その背後にある考え方が何であるかがわかりませんでしたBIT。私が読んだチュートリアルは

について理解してもらうのを手伝ってくださいBIT。

4

4 に答える 4

7

トップコーダーの記事はそれほど明確ではありません。ここに、あなたの出発点となる大きなアイデアがあります。

BIT は、整数 から整数 への密なマップを格納するのに適していますf[i]。ここi >= 1で、マップ ドメインの範囲にわたる合計を取得することに関心があります。つまりsum_{i = a..b} f[i]、任意aの およびの場合bです。C でコーディングしている場合、これは次のようになります。

sum = 0; for (i = a; i <= b; i++) sum += f[i];

密集とはf[i]>0、ほとんどのことを意味しiます。まばらなマップがある場合は、他のデータ構造の方が適しています。

BIT を使用すると、合計の実行時間が に比例するのでb - aはなく、 に比例するように、この計算を高速化できますlog(b+a)。新しい要素を挿入する時間も同様です。

これを行うために、BIT はg[k]ではなく別のマップを格納しf[i]ます。の内容はg巧妙な方法で定義されています。 

g[k] = sum_{i = k - d + 1 .. k} f[i]

ここでdは の値でk、最下位ビット以外はすべてゼロに設定されています。たとえば、 の場合k=8、d=8. もしk=14、その後d=2、など。

明示的なツリーがないことに注意してください。チュートリアルの図に示すように、ツリーは論理的です。唯一のストレージは配列gです。

なぜこれが良い考えなのですか？を見つけるには、 のほとんどの要素をsum_{i = a..b} f[i]合計するだけでよいことがわかります。これらの要素は、およびのバイナリ 1 ビットを分析することによって決定できます。詳細はチュートリアルに示されています。 2 ceiling(log(b+a))gab

最も単純な例: が必要な場合はsum_{i = 1..p} f[i]、一連のインデックスp_1、p_2、...を作成します。p_nここでp_1 = p、 とp_(i+i)は から最下位の 1 ビットを削除することによって形成されp_iます。したがってn、 は の 2 進数表現の 1 の数よりも 1 つ少なくなりpます。あとは計算するだけ

sum_{k = p_1, p_2 ... p_n} g[k]

これについて少し実験して考えてみると (しゃれが意図されています)、なぜそれが機能するのかがわかります。

于 2013-02-20T01:49:10.620 に答える
2

バイナリインデックスツリーはフェンウィックツリーとも呼ばれます。バイナリインデックスツリーはフェンウィックツリーに比べてあまり知られていないと思います。したがって、バイナリインデックスツリーを見つけると、マテリアルが少なくなりますが、これは私の気持ちです。

簡単に言うと、フェンウィックツリー（別名バイナリインデックスツリー）は、要素のシーケンスを維持するデータ構造であり、O（logn）時間内の任意の範囲の連続する要素の累積合計を計算できます。単一の要素の値を変更するには、O（logn）時間も必要です。この構造は、n個の要素の単純な配列と同じ量のストレージを必要とするという意味でスペース効率が高くなっています。

上記を説明するための実際的な例は、ネット上のさまざまな場所で見つけることができます。

http://codeforces.com/blog/entry/619

http://michaelnielsen.org/polymath1/index.php?title=Updating_partial_sums_with_Fenwick_tree

そして、ネット上にはもっとたくさんの例があります...

于 2013-02-25T14:19:36.787 に答える
1

バイナリ インデックス ツリーは、プレフィックスによって値を取得できるデータ構造です。バイナリ インデックス ツリーについての私の理解では、多かれ少なかれ試行に似ています。たとえば、1323、1697、1642 の 3 つの数字があるとします。これらの数字をツリーに格納できます。

1-3-2-3  
 -6-9-7  
   -4-2

ここで、各ノードは 10 の位を表します。今では、電話帳で名前を 1 文字ずつ検索できるように、任意の番号を検索できます。ここでは、各ノードは 10 単位ですが、異なるベースを選択して表現をできるだけコンパクトにすることができます。たとえば、各ノードが 4 ビットを格納する場合、基数 8 を使用できます。

このデータ構造により、数値を簡単に追加できます。たとえば、番号 #1 (1323) と #3 (1642) を追加するとします。次に、各数値を表すリーフから開始し、基数 (ここでは 10) の累乗を掛けながら上に向かって作業します: 3+2、(2+4)*10、(6+3)*100、次に (1+1)*1000。

于 2013-02-19T23:12:48.697 に答える