0

これは、インデックス 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 多い場合もあれば、実際の答えである場合もあります。

私を助けてください。

4

1 に答える 1

1

アクセス数は、2 進表現で正確に 1 の数です。これは、1000000 より小さい数値が当てはまらない場合に何かを出力する短い Python (私が怠け者だからという理由だけで Python) スクリプトです。

def count(x):
  ones = 0
  for ch in bin(x): 
    if ch =='1':
      ones = ones + 1
  return ones

access = 0;
for y in range(1000000):
  access = 0
  x = y
  while x > 0:
    x = x -(x & (-x))
    access = access + 1
  if count(y) != access:
    print "Wrong:"+str(y)
于 2016-10-15T12:20:08.250 に答える