Фенвик дерево Суммы запрос

Question

Это код запроса суммы от индекса 0 до индекса X

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

У меня есть два массива BIT[] and a[]. Я сохраняю значения из массива a в BIT для запросов. Теперь, согласно циклу, мы делаем добавление значения в индексе X, а затем изменяем индекс, удаляя из него последний бит.

Для, например, если я позвоню запрос (14) будет выполняться следующим образом:

Sum = BIT [14] + БИТ [12] + БИТ [8]

Он остановится после индекса 8 как 8 1000, и после удаления последнего бит он становится 0 и заканчивается концом. Таким образом, это означает для индекса 14 I.e 1110 Я получаю доступ к массиву 3 раза, I.e - количество установленных бит. Но я проверил длинные биты, это не удалось, например, 1000110111011101100 бит набора равен 11, но ответ 12. Так есть ли другой способ рассказать, сколько раз я обращаюсь к массиву во время выполнения запроса суммы, видя двоичное значение индекса I?

Я не могу понять это. Я пробовал много случаев, для некоторых это меньше на 1, для некоторых это больше на 1, а для некоторых это на самом деле ответ.

Пожалуйста, помогите мне.

Answer 1

Число обращений - это точно число единиц в двоичном представлении. Вот короткий Python (Python только потому, что я ленивый) скрипт, который будет печатать что-то, если это не будет иметь место любое число меньше 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)