3

我的问题涉及二进制索引树（Fenwick Trees）中更新步骤背后的全部原因。因此，当以特定增量更新我们的数组时，在特定位置，更新如下所示：

void updateBIT(int BITree[], int n, int index, int val)
{
    // index in BITree[] is 1 more than the index in arr[]
    index = index + 1;

    // Traverse all ancestors and add 'val'
    while (index <= n)
    {
       // Add 'val' to current node of BI Tree
       BITree[index] += val;

       // Update index to that of parent in update View
       index += index & (-index);
    }

我的问题是index += index & (-index);零件。请注意，我理解这index & (-index)一点，尤其是在查询树的上下文中。

我已经使用此索引更新规则手动尝试了几个示例，但我无法找到添加背后的逻辑index & (-index)，以便转到下一个需要更新的节点。

从我起床到这一点，iBIT 中的一个节点对数组中的原始值“负责”，范围为[i - i & (-i) + 1, i]，因此这意味着任何节点都将落入这种形式的范围内。具体来说，据我了解，当想要更新k原始数组中的位置时，我们遵循以下步骤（从概念上讲，不是在实际代码中）：

  • 迭代0：更新BIT[k + 1]（索引1在 BIT 数组中移动）。在迭代0时，我们更新了我们正在查看的索引，所以我假设我们正在寻找负责 node 的下一个最小间隔k，因此我们需要找到下一个索引iwhere i - i & (-i) < k < i。i通过将当前索引增加 来查找此索引k & (-k)。

其余的迭代以相同的方式发生，直到我们超出限制。我已经手动尝试了许多示例，但我仍然不明白为什么添加i & (-i)会将我们带到正确的下一个节点。我在网上找到的每一个教程，包括视频，在这件事上都是完全不靠谱的。

这里有几个关于BITs的相关问题，请不要在仔细阅读之前将它们与我的合并。据我所知，这个特定的问题尚未得到解答。

4

1 回答 1

0

所以，让我尝试通过一个简单的例子来解释上述场景。

让我们来吧i = 12。现在我们更新BIT[12]. 现在下一步要根据算法进行更新i += i&(-i)。

二进制中的 12 是多少 = 01100. 设置的最后一位是2，值为2^2= 4 （如您所知

0th bit value is 2^0 = 1
1st bit value is 2^1 = 2
2nd bit value is 2^2 = 4.

以类似的方式处理其他位。

所以现在我们要更新的下一个索引是12 + 4 = 16. 即BIT[16]。

现在这是关于系统如何工作的。让我试着用简单的话来解释为什么这种技术有效。

假设我需要更新index = 1，假设 MAX 数组值为 8。那么我将更新所有索引1,2,4,8。

现在，假设我需要更新index = 3. 所以我将更新数组索引3,4,8。

因此，您会看到到目前为止如何BIT[4]从数组 index 中获得所有值的总和1 to 4。

现在假设您需要获取前 4 个数字的总和，您只需这样做BIT[4]，您将遍历索引4,0。简而言之，您不会遍历1,2,3. 正如我们所见，这些索引是如何由于位操作而被覆盖的。

希望这可以帮助！

于 2018-08-01T20:18:27.457 回答