これは、インデックス 0 からインデックス X までの合計クエリのコードです。
Int query(int x){
Int sum=0;
for(; x>0; x -= x &(-x) )
sum += BIT[x];
Return sum;
}
2 つの配列がありますBIT[] and a[]
。クエリ用に配列 a から BIT に値を格納します。ループに従って、インデックス X に値を追加し、最後に設定されたビットを削除してインデックスを変更します。
たとえば、 query(14) を呼び出すと、次のように実行されます。
合計 = ビット [14] + ビット [12] + ビット [8]
インデックス 8 の後に 8 のまま停止し1000
、最後のビットを削除すると 0 になり、ループが終了します。つまり、インデックス 141110
の場合、つまり、配列に 3 回アクセスすることを意味します。つまり、セットされたビットの数です。しかし、長いビットをチェックしました。たとえば、1000110111011101100
セットビットは 11 ですが、答えは 12 で失敗しました。インデックス I のバイナリ値を確認することで、合計クエリの実行中に配列にアクセスした回数を知る他の方法はありますか?
私はそれを理解することはできません。私は多くのケースを試しましたが、1 少ない場合もあれば、1 多い場合もあれば、実際の答えである場合もあります。
私を助けてください。