我在算法的源代码中发现了这个循环.我认为这些问题的细节在这里是不相关的,因为这是解决方案的一小部分.
void update(int i,int value,int array[],int n) {
for(; i < n; i += ~i & (i + 1)) {
array[i] += value;
}
}
我真的不明白在for循环中会发生什么,这是一种技巧吗？我发现了类似的Fenwick树,但是它们看起来和我在这里有些不同.
任何想法这个循环意味着什么？
另外,发现这个：
“Bit Hack#9.隔离最右边的0位.
y =〜x& (x 1)
“
解决方法
你是对的：bit-hack〜我& (i 1)应该计算一个全为二进制0的整数,除了对应于i的最右边的零位的一个,它被设置为二进制1.
所以在for循环的每次通过结束时,它将此值添加到自身中.由于i中的相应位为零,这具有设置它的效果,而不影响i中的任何其他位.这将严格增加每次通过i的值,直到我溢出(或者如果您开始使用i <0,则为-1).在上下文中,您可能希望在i> = 0时调用它,n设置在你的索引离开数组之前终止循环.
整体功能应该具有通过从最初到最高有效值的i的原始值的零位进行迭代的效果,逐个设置它们,并递增数组的相应元素.
芬威克树是一种有效累积和查询统计数据的聪明方式;正如你所说,他们的更新循环看起来有点像这样,并且通常使用可比较的位黑客.必须有多种方式来完成这种点阵,所以您的源代码当然可以更新Fenwick树,或者可比较的东西.
