最近、Fenwick Tree (Binary Indexed Tree)データ構造について学びました。
クエリを実行すると、(idx & -idx) を減算する理由が理解できます。ただし、値を更新するときに (idx & -idx) を追加する理由がよくわかりません。
言い換えれば、単一の要素 x を更新することによって影響を受けるすべての間隔を更新する必要があることはわかっています。また、BIT[x] が最初に更新されることはわかっていますが、次のインデックスが更新される理由を理解できません。ビット[x + (x & -x)]
ありがとう。
ここに良い説明があります: http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees
重要なアイデアは、f(i) がインデックス i での頻度である場合、t(i) はすべての累積頻度 (i - (r - 1)) .. i であり、r は i の最小設定ビットです。r = i & -i として r を計算できます。
[編集: 上記で、(r - 1) を (2^r - 1) と誤って記述していました。]
たとえば、i = 12 = 1100_2 の場合、r = 100_2 および t(i) = f(1001_2) + f(1010_2) + f(1011_2) + f(1100_2) = f(9) + f(10) + f(11) + f(12)。
0 .. i から累積度数を計算するときは、基本的に i での t 値を合計し、i で最小セット ビットを削除し、i で最小セット ビットを 2 つ削除して ... というように、ビットがなくなるまで繰り返します。
たとえば、i = 12 = 1100_2 の場合、t(1100_2) + t(1000_2) が必要です。
したがって、f(i) の値を変更すると、影響を受けるすべての t 値を変更する必要があります。これらは、最後のインデックスを超えるまで、t(i)、t(i + r)、2t(i + r)、4t(i + r) などです。これらは、インデックス j >= i の累積度数計算で調べる、影響を受ける t 値です。
[編集: j_random_hacker による修正に対応して、最後の段落の「影響を受ける t 値」シーケンスを修正しました。]