Fenwick Baum Sum Abfrage

Question

Dies ist der Code für die Summe Abfrage von Index 0 bis Index X

Int query(int x){ 
Int sum=0; 
for(; x>0; x -= x &(-x)) 
    sum += BIT[x]; 
Return sum; 
} 

Ich habe zwei Arrays BIT[] and a[]. Ich speichere die Werte von Array A zu BIT für Abfragen. Nun fügen wir gemäß der Schleife einen Wert am Index X hinzu und ändern dann den Index, indem wir das letzte gesetzte Bit daraus entfernen.

Für zB wenn ich Abfrage nennen (14) wird wie folgt ausführen:

Summe = BIT [14] + BIT [12] + BIT [8]

Es wird aufhören nach Index 8 wie 8 ist 1000 und nach dem Entfernen des letzten Bits wird es 0 und Schleife endet. Das heißt, für Index 14 Ie. 1110 Ich greife auf das Array 3 mal, IE ist die Anzahl der gesetzten Bits. Aber ich habe nach langen Bits gesucht, es ist fehlgeschlagen für zB 1000110111011101100 gesetzte Bits sind 11 aber die Antwort ist 12. Gibt es eine andere Möglichkeit zu sagen, wie oft ich während der Ausführung der Summenabfrage auf das Array zugreife, indem ich den Binärwert eines Index I sehe?

Ich kann es nicht herausfinden. Ich habe viele Fälle ausprobiert, für einige ist es weniger als 1, für einige ist es mehr als 1 und für einige ist es tatsächlich die Antwort.

Bitte helfen Sie mir.

Answer 1

Anzahl der Zugriffe ist genau die Anzahl der Einsen in Binärdarstellung. Hier ist der kurze Python (Python, nur weil ich faul bin) Skript, das etwas drucken würde, wenn es nicht der Fall ist jede Zahl kleiner als 1000000

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)