Сумма дерева Фенвика

Question

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

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

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

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

Сумма = БИТ [14] + БИТ [12]+ БИТ [8]

Он остановится после индекса 8, так как 8 1000 и после удаления последнего бита он становится равным 0 и цикл заканчивается. Так что значит для индекса 14 т. Е. 1110 Я обращаюсь к массиву 3 раза, т.е. это количество установленных бит. Но я проверил на длинные биты, это не удалось, например, для 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)