66

For example:

int get(int i) {
    int res = 0;
    while (i) {
        res = (res + tree[i]) % MOD;
        i -= ( (i) & (-i) );
    }
    return res;
}

A tree update function:

void update(int i, int val) {
    while (i <= m) {
        tree[i] = (tree[i] + val) % MOD;
        i += ( (i) & (-i) );
    }
}

Can you please explain what they do in the code by using ( (i) & (-i) )?

4

3 回答 3

94

让我假设使用二进制补码表示负值。在这种情况下，-i可以计算为(~i)+1（翻转位，然后加 1）。

例如，让我考虑i = 44. 然后，在二进制中，

i           = 0000 0000 0000 0000 0000 0000 0010 1100
~i          = 1111 1111 1111 1111 1111 1111 1101 0011
-i = (~i)+1 = 1111 1111 1111 1111 1111 1111 1101 0100
(i) & (-i)  = 0000 0000 0000 0000 0000 0000 0000 0100

如您所见，可以使用 1 来计算最小位 1 (i) & (-i)。

于 2016-03-08T07:19:39.297 回答
21

如果有人也想要更一般的证明，

假设x格式为 a10 k（这里的意思是一些位串 a，后跟一个 1，然后是 k 个零）。

-x是（根据定义）与 相同的东西~x + 1，所以

  • x & -x = (填写)
  • a10 k & -(a10 k ) = (否定的定义)
  • a10 k & ~(a10 k ) + 1 = (应用反转)
  • a10 k & ~a01 k + 1 = (加 1)
  • a10 k & ~a10 k =（某事物与其逆事物之间的与）
  • 0 w 10 k

所以我们只剩下我们假设存在的那个最右边的 1。

关于 的形式的假设x忽略了 的情况x = 0，在这种情况下，结果显然仍然为零。

于 2016-03-08T15:20:17.393 回答
13

这两个函数是二进制索引树（Fenwick 树）数据结构的修改实现。
这是补充 MikeCAT 答案的两张图片，显示了我如何针对不同的值进行变量更新。

“get”函数：
为了简化表示，假设函数输入的最大值为 15。其上编号为t的节点表示树数组中的tree[t]。 如果您为i调用get函数，则返回值是tree[i]的总和加上它们在数组中的索引是i的父级的所有树数组元素的总和
在此处输入图像描述

在图片中，除了零。
这里有些例子：

get(15) = tree[15] + tree[14] + tree[12] + tree[8]
get(14) = tree[14] + tree[12] + tree[8]
get(13) = tree[13] + tree[12] + tree[8]
get(12) = tree[12] + tree[8]
get(11) = tree[11] + tree[10] + tree[8]
get(10) = tree[10] + tree[8]
get(9) = tree[9] + tree[8]
get(8) = tree[8]
get(7) = tree[7] + tree[6] + tree[4]
get(6) = tree[6] + tree[4]
get(5) = tree[5] + tree[4]
get(4) = tree[4]
get(3) = tree[3] + tree[2]
get(2) = tree[2]

上图中节点标签上的数字具有每个节点的父节点的属性是该节点标签减去最不重要的一个 1（在@MikeCAT 答案上解释得很好）
“更新”功能：
为了简单起见，假设树数组的最大长度为 16。
更新函数有点棘手。 它将val添加到tree[i]以及它们的索引是图片中带有标签i的节点的父节点的所有树元素。
二叉索引树

update(16, val) --> tree[16] += val;
update(15, val) --> tree[15] += val, tree[16] += val;
update(14, val) --> tree[14] += val, tree[16] += val;
update(13, val) --> tree[13] += val, tree[14] += val; tree[16] += val;
update(12, val) --> tree[12] += val, tree[16] += val;
update(11, val) --> tree[11] += val, tree[12] += val, tree[16] += val;
update(10, val) --> tree[10] += val, tree[12] += val, tree[16] += val;
update(9, val)  --> tree[9] += val, tree[10] += val, tree[12] += val, tree[16] += val;
update(8, val)  --> tree[8] += val, tree[16] += val;
update(7, val)  --> tree[7] += val, tree[8] += val, tree[16] += val;
update(6, val)  --> tree[6] += val, tree[8] += val, tree[16] += val;
update(5, val)  --> tree[5] += val, tree[6] += val, tree[8] += val, tree[16] += val;
update(4, val)  --> tree[4] += val, tree[8] += val, tree[16] += val;
update(3, val)  --> tree[3] += val, tree[4] += val, tree[8] += val, tree[16] += val;
update(2, val)  --> tree[2] += val, tree[4] += val, tree[8] += val, tree[16] += val;
update(1, val)  --> tree[1] += val, tree[2] += val, tree[4] += val, tree[8] += val, tree[16] += val;
于 2016-03-09T09:38:51.343 回答