时间戳

首页 > 解决方案 > Fenwick 树中的点更新

data-structures - Fenwick 树中的点更新

问题描述

我很难理解将 LSB 添加到当前索引如何为我们提供包含给定点的下一个位置。

void update(int k, int x) {
    while (k <= n) {
        tree[k] += x;
        k += k&-k; // adding LSB (least significant bit)
    }
}

任何人都可以向我解释或参考一些资源吗？我看到的所有资源都只是告诉你它有效，但没有解释为什么。我知道查询是如何工作的。

谢谢。

PS我在这里看到了同样的问题，但我还是不明白，因为他们并没有真正解释。

标签： data-structuresfenwick-tree

解决方案

从根本上掌握Fenwick Tree数据结构可能相当棘手，但是一旦您了解了基础数学，您应该擅长它。因此，我将尝试解释有关Fenwick Trees的所有方式和原因。

Fenwick Tree 基于数组索引的二进制表示

首先，你应该坚定地理解的是：

Fenwick 树的概念基于一个事实，即每个整数都可以表示为二进制数，即 2 的不同幂的和，并且该表示将是唯一的。例如，整数 14 可以表示为 2 3 +2 2 +2 1。

请注意，“不同”是此定义中的重要关键字，因此您不应将 14 表示为 2 3 +2 1 +2 1 +2 1。

芬威克树的种植方式

我不会在这里实现Fenwick Tree 填充算法（你说，你了解树是如何填充的，此外，它与问题无关）；但是，我要强调一个事实，Fenwick Tree [大部分] 是通过数组实现的，在某种程度上，fenwick-tree数组中的每个槽都保存一个值，该值是原始数组的范围之和，其中：

  1. 该范围内的右索引是k本身（这个槽是右边界）；
  2. 该范围内的元素数是该索引的二的幂和表示的最小加数（因此，您应该从右到左计算该元素的数量，以便获得有问题的范围）。

PS 如果芬威克树在索引 24 处存储了一些n值，这意味着原始数组中区间 [17, 24] 的总和将为n。

问：为什么 17 是左边界？
答：因为，24 是 2 4 +2 3，这个表达式的最小加数是 2 3 = 8。现在，根据上面给出的定义，Fenwick Tree数组中索引 24 处元素的总和范围，将包含 8 个元素，如果右边界恰好位于索引 24 本身，则从右到左的 8 个连续元素将使我们到达左边界，即索引 17；因此，我们在包含范围 [17, 24] 中有 8 个元素，索引 24 处的值将是n，它是 [17, 24] 范围内元素的总和。

这张图片甚至可以清楚地说明我上面写的内容：

在此处输入图像描述

重要的提示：

将整数表示为 2 的不同幂的总和，源于二进制数字系统的原理。

例如，1011 可以写成 2 3 +2 1 +2 0。

在二进制表示中，最左边的列构成 2 的 3 次方，最右边的列构成 2 的 0 次方。在二进制表示中，2 的次方从最右边的列向左每一步增加 1。

如果您了解二进制数字系统，您应该了解，当将某个数字N表示为两个不同幂的和时，该和中的最小数字与N的二进制表示中的部分相同，从最低有效位 (LSB) 并以该二进制表示的最右边数字结尾，这也与 2 的indexOf (LSB)-1 次幂相同（如果您从右边开始用 1 索引您的二进制数）或indexOf (LSB)（如果你用 0 索引你的号码）。

这一切带来了什么？

更快的范围查询

了解范围查询如何在 Fenwick 树中工作。

我希望您了解我们需要范围查询的前缀总和。

为了计算 的前缀总和，original[0, index]而不是遍历整个数组，您现在只需从该索引向下级联到相应的Fenwick Tree ，并不断从这些索引处的值中删除 LSB，同时不断总结值在所有这些索引处（它们是原始数组范围的总和）。

这看起来像：

int prefixSum(int index) {
    int sum = 0;
    while(index!=0) {
        sum+=fenwickTree[index];
        index = index - LSB(index);
    }
    return sum;
}

问：为什么会这样？
A : 我认为现在应该很明显了，但如果仍然没有，那么请密切注意我们为什么要删除 LSB(index)。我们这样做是因为在计算前缀 sumfenwickTree[index]时添加到当前 sum之后，正如我们在上面已经解释的那样，存储原始数组间隔的另一个切片的下一个 slot 将位于，因为在Fenwick Tree中，索引k存储长度为 [2 LSBIndexOf(toBinary(k))-1 , k]的区间index = index - LSB(index)

因此，根据我们刚刚展示的内容（级联、求和和index-LSB(index)），使用Fenwick 树，索引 11 的前缀和（例如）将计算为：

prefixSum = fenwickTree[11] + fenwickTree[10] + fenwickTree[8]

因为：

  1. fenwickTree[11]存储总和original[11]（奇数索引仅存储这些索引处的值）；
  2. fenwickTree[10]存储总和original[9,10]；
  3. fenwickTree[8]存储总和original[1, 8]。

您基本上有 3 个切片要总结：[1,8]、[9,10] 和 [11]。

更快的点更新

了解点更新如何在 Fenwick 树中工作。

我认为，现在很明显，点更新为什么以及如何工作 - 就 LSB 而言，它是范围查询的相反操作- 而不是删除 LSB（索引），您将添加 LSB（索引），现在级联 UP到索引并更新Fenwick Tree中的相应索引。

例如，如果我们想在索引 9 处添加一个值，则必须找出所有负责该索引的槽，并且必须更新它们。我们必须从索引 9 元素的 LSB 开始获取数字，并且必须将其添加到索引 9 处的值。我们必须不断重复此操作，直到到达 LSB 是该索引本身的数字的槽。而已。

void update(int i, int x) {
    while (i <= n) {
        fenwickTree[i] += x;
        i += LSB(i); //this will give you the next slot which is used as an addend
    }
}

我真的希望这对您有所帮助并阐明您的理解。

推荐阅读