66

例えば：

int get(int i) {
    int res = 0;
    while (i) {
        res = (res + tree[i]) % MOD;
        i -= ( (i) & (-i) );
    }
    return res;
}

ツリー更新機能:

void update(int i, int val) {
    while (i <= m) {
        tree[i] = (tree[i] + val) % MOD;
        i += ( (i) & (-i) );
    }
}

を使用して、コードで何をするのか説明していただけます( (i) & (-i) )か?

4

3 に答える 3

94

負の値を 2 の補数で表すとします。この場合、(ビットを反転してから 1 を加算)-iとして計算できます。(~i)+1

たとえば、考えてみましょうi = 44。次に、バイナリで、

i           = 0000 0000 0000 0000 0000 0000 0010 1100
~i          = 1111 1111 1111 1111 1111 1111 1101 0011
-i = (~i)+1 = 1111 1111 1111 1111 1111 1111 1101 0100
(i) & (-i)  = 0000 0000 0000 0000 0000 0000 0000 0100

ご覧のとおり、1 である最小ビットは を使用して計算できます(i) & (-i)。

于 2016-03-08T07:19:39.297 に答える
21

より一般的な証明が必要な場合に備えて、

xが a10 kという形式であると仮定します(ここでは、ビット文字列 a の後に 1 が続き、その後に k 個のゼロが続くことを意味します)。

-xは (定義により) と同じものな~x + 1ので、

  • x & -x = (記入)
  • a10 k & -(a10 k ) = (否定の定義)
  • a10 k & ~(a10 k ) + 1 = (反転を適用)
  • a10 k & ~a01 k + 1 = (1 を追加)
  • a10 k & ~a10 k = (何かとその逆数の間の AND)
  • 0週10キロ

したがって、存在すると仮定した右端の 1 だけが残ります。

の形式に関する仮定ではx、 の場合が除外されx = 0ます。この場合、結果は明らかにゼロのままです。

于 2016-03-08T15:20:17.393 に答える
13

この 2 つの関数は、バイナリ インデックス ツリー (フェンウィック ツリー)データ構造 の変更された実装です。これは、さまざまな値に対してi変数が
どのように更新されるかを示す MikeCAT の回答を補足する 2 つの図です。「get」関数: 表現を簡単にするために、関数の入力の最大値を 15 と仮定します。番号tを持つノードは、ツリー配列内のツリー [t]を表します。iに対してget関数 を呼び出すと、返される値は、tree[i]の合計と、配列内のインデックスがiの親であるすべてのツリー配列要素の合計です。



ここに画像の説明を入力

写真では、ゼロを除いて。
ここではいくつかの例を示します。

get(15) = tree[15] + tree[14] + tree[12] + tree[8]
get(14) = tree[14] + tree[12] + tree[8]
get(13) = tree[13] + tree[12] + tree[8]
get(12) = tree[12] + tree[8]
get(11) = tree[11] + tree[10] + tree[8]
get(10) = tree[10] + tree[8]
get(9) = tree[9] + tree[8]
get(8) = tree[8]
get(7) = tree[7] + tree[6] + tree[4]
get(6) = tree[6] + tree[4]
get(5) = tree[5] + tree[4]
get(4) = tree[4]
get(3) = tree[3] + tree[2]
get(2) = tree[2]

上の図のノードのラベルの数字には、各ノードの親がそのノード ラベルから最下位のラベル 1 を引いたものであるというプロパティがあります (@MikeCAT の回答で非常によく説明されています )
。ツリー配列
の最大長は 16 です 。update関数は少しトリッキーです。tree[i]と、そのインデックスが図のラベルiを持つノードの親であるすべてのツリー要素にvalを 追加します。

バイナリ インデックス ツリー

update(16, val) --> tree[16] += val;
update(15, val) --> tree[15] += val, tree[16] += val;
update(14, val) --> tree[14] += val, tree[16] += val;
update(13, val) --> tree[13] += val, tree[14] += val; tree[16] += val;
update(12, val) --> tree[12] += val, tree[16] += val;
update(11, val) --> tree[11] += val, tree[12] += val, tree[16] += val;
update(10, val) --> tree[10] += val, tree[12] += val, tree[16] += val;
update(9, val)  --> tree[9] += val, tree[10] += val, tree[12] += val, tree[16] += val;
update(8, val)  --> tree[8] += val, tree[16] += val;
update(7, val)  --> tree[7] += val, tree[8] += val, tree[16] += val;
update(6, val)  --> tree[6] += val, tree[8] += val, tree[16] += val;
update(5, val)  --> tree[5] += val, tree[6] += val, tree[8] += val, tree[16] += val;
update(4, val)  --> tree[4] += val, tree[8] += val, tree[16] += val;
update(3, val)  --> tree[3] += val, tree[4] += val, tree[8] += val, tree[16] += val;
update(2, val)  --> tree[2] += val, tree[4] += val, tree[8] += val, tree[16] += val;
update(1, val)  --> tree[1] += val, tree[2] += val, tree[4] += val, tree[8] += val, tree[16] += val;
于 2016-03-09T09:38:51.343 に答える