algorithm - Fenwick Trees 中的更新步骤

Question

我的问题涉及二进制索引树(Fenwick 树)中更新步骤背后的完整推理。因此，当以一定的增量更新我们的数组时，在某个位置，更新是这样的:

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) 背后的逻辑。以便转到下一个需要更新的节点。

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

• 迭代 0 : 更新BIT[k + 1] (索引由 1 在 位数组)。虽然仍在迭代 0 ，我们更新我们的索引 看着，所以我假设我们正在寻找下一个最小的 负责节点 k 的区间, 因此我们需要找到 下一个索引 i其中 i - i & (-i) < k < i .查找此索引 i经过 将当前索引增加 k & (-k) .

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

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

Answer 1

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

让我们取 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] 是如何得到数组索引 1 到 4 中所有值的总和的。

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

希望这对您有所帮助!