(数字和-number)在位编程中是什么意思? [英] What does (number & -number) mean in bit programming?

问题描述

例如:

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

树更新功能:

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

您能否使用( (i) & (-i) )在代码中解释它们的作用?

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

推荐答案

这两个函数是二叉索引树(Fenwick树)数据结构.
以下是两张图片来补充MikeCAT的答案，它们显示了 i 变量如何针对不同的值进行更新.

获取"功能:
为了简化表示，假设函数中输入的最大值为15.

其中编号为 t 的节点表示树数组中的 tree [t] .
如果您为 i 调用 get 函数，则返回的值是 tree [i] 的总和加上所有 tree 的总和数组元素，它们在数组中的索引是图片中 i 的父元素，但零除外.
以下是一些示例:

This two functions are a modified implementation of a Binary index tree (Fenwick tree) data structure.
Here is two pictures to supplement MikeCAT's answer showing how i variable updates for different values.

The "get" function:
For assume max value in of input in function is 15 for simplicity of representation.

A node with number t in on it represents tree[t] in the tree array.
If you call get function for i the returned value is sum of tree[i] plus sum of all tree array elements that their index in the array is a parent of i in the picture, except zero.
Here are some examples:

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答案中解释得很好) 更新"功能:
为了简化图片，假设 tree 数组的最大长度为16.
更新功能有点棘手.

它将 val 添加到 tree [i] 以及所有 tree 元素，它们的索引是带有标签 i 在图片中.

Numbers on the labels on nodes in the above picture, has the property that each node's parent is that node label minus the least significant one 1(explained very well on @MikeCAT answer) The "update" function:
For simplicity of picture, let assume that the max length of the tree array is 16.
The update function is little bit trickier.

It adds val to tree[i] and all tree elements that their index is parent of the node with label i in the picture.

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;

这篇关于(数字和-number)在位编程中是什么意思?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！