分域树求和查询

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处添加值，然后通过移除最后一个set位来改变索引。

例如，如果我调用query(14)，它将执行如下:

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

它将在索引8之后停止，因为8是1000，在删除最后一位后它变成0，循环结束。这意味着对于索引14，也就是1110，我访问数组3次，也就是集合位的个数。但是我检查了长位，它失败了，例如1000110111011101100集位是11，但答案是12。那么是否有其他方法可以通过查看索引I的二进制值来告诉我在执行sum查询期间访问数组的次数?

我想不明白。我试过很多情况，有些比原来少1，有些比原来多1，有些就是答案。

请帮帮我。

Answer 1

访问数就是二进制表示的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)