0

这是从索引 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 处添加值，然后通过从中删除最后设置的位来更改索引。

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

总和= BIT[14] + BIT[12]+ BIT[8]

它将在索引 8 之后停止，因为 8 是1000，并且在删除最后一位之后它变为 0 并且循环结束。所以这意味着对于索引 14 即1110我访问数组 3 次，即是设置位的数量。但是我检查了长位，它失败了，例如1000110111011101100设置位是 11 但答案是 12 。那么有没有其他方法可以通过查看索引 I 的二进制值来判断在 sum 查询执行期间访问数组的次数？

我想不通。我尝试了很多情况，对于某些情况，它小于 1，对于某些情况，它大于 1，而对于某些情况，它实际上是答案。

请帮帮我。

4

1 回答 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)
于 2016-10-15T12:20:08.250 回答