3

我在互联网上阅读了 2-3 个二叉索引树（又名 Fenwick 树）教程，但我不明白它的实际作用以及背后的想法是什么BIT。我读的教程是

请帮助我让我了解BIT.

4

4 回答 4

7

顶级编码员文章不是很清楚。这是一个可以帮助您入门的大创意。

BITs 非常适合存储从整数到整数的密集映射f[i]，其中i >= 1您有兴趣检索映射域范围内的总和，即sum_{i = a..b} f[i]任意a和b。如果你用 C 编码，这将是：

sum = 0; for (i = a; i <= b; i++) sum += f[i];

密集我的意思f[i]>0是大多数i。如果你有一个稀疏的地图，其他数据结构会更好。

BIT 可让您加快计算速度，从而使总和的运行时间（而不是与 成正比b - a）与 成正比log(b+a)。插入新元素的时间类似。

为此，BIT 存储不同的地图g[k]而不是f[i]. 的内容g以巧妙的方式定义。 

g[k] = sum_{i = k - d + 1 .. k} f[i]

其中d是除k最低位之外的所有位设置为零的值。例如，如果k=8，那么d=8。如果k=14, 那么d=2, 等等

请注意，没有明确的树。树是合乎逻辑的，如教程图片所示。唯一的存储是数组g。

为什么这是个好主意？事实证明，要找到sum_{i = a..b} f[i]，您只需要总结 的最多2 ceiling(log(b+a))元素g。这些元素可以通过分析 和 的二进制 1 位来a确定b。详细信息显示在教程中。

最简单的例子：如果你想要sum_{i = 1..p} f[i]，则构造一系列索引p_1, p_2, ...p_n其中p_1 = p和p_(i+i)是通过从 中删除最低位 1 位形成的p_i。因此n比 的二进制表示中的 1 的个数少一p。现在只计算

sum_{k = p_1, p_2 ... p_n} g[k]

如果您尝试并稍微考虑一下（双关语），您就会明白它为什么有效。

于 2013-02-20T01:49:10.620 回答
2

二叉索引树也称为 Fenwick 树，我认为二叉索引树与 Fenwick 树相比鲜为人知，所以当我们找到二叉索引树时，我们发现的材料更少，但这只是我的感觉！

简而言之，Fenwick 树（又名二叉索引树）是一种维护元素序列的数据结构，并且能够在 O(logn) 时间内计算任意范围的连续元素的累积和。更改任何单个元素的值也需要 O(logn) 时间。该结构是节省空间的，因为它需要与 n 个元素的简单数组相同的存储量。

可以在网上的各个地方找到一个用于说明上面的实际示例，即

http://codeforces.com/blog/entry/619

http://michaelnielsen.org/polymath1/index.php?title=Updating_partial_sums_with_Fenwick_tree

网上还有更多的例子......

于 2013-02-25T14:19:36.787 回答
1

二叉索引树是一种允许通过前缀检索值的数据结构。我对二叉索引树的理解是它们或多或少类似于尝试。例如，假设您有三个数字 1323、1697 和 1642。您可以将这些数字存储在树中：

1-3-2-3  
 -6-9-7  
   -4-2

其中每个节点代表一个 10s 的地方。现在您可以查找任何号码，就像您可以在电话簿中逐个字母地查找姓名一样。在这里，每个节点都是 10s，但您可以选择不同的基数以使表示尽可能紧凑。例如，您可以使用 base 8，在这种情况下，每个节点存储 4 位。

这种数据结构使您可以轻松地添加数字。例如，假设您要添加数字 #1 (1323) 和 #3 (1642)。然后从代表每个数字的叶子开始向上工作，乘以基数的幂（这里是 10）：3+2，然后是 (2+4)*10，然后是 (6+3)*100，然后 (1+1)*1000。

于 2013-02-19T23:12:48.697 回答
0

BIT 是一个非常奇特的东西，理解它的关键是知道快速分段算法是如何工作的。

快速分段算法和数据结构的基本思想是“跳过”一些东西。考虑一个整数数组 a[1..n]。现在你想要另一个数组 C[1..n]，在 C [i] 包含 C[i],C[i-1] 到 C[k(i)] 的总和（k 是某种魔术函数 (OO) ）。

当你想得到 a[1..i] 的总和时，你可以这样写：

    int get_sum(int i) {
        if (i == 0)
            return 0;
        return get_sum(k(i)-1)+C[i];
    }

这很容易理解是吗？我们只使用 C[i] = sum(a[k(i)..i])而不是遍历整个段。当我们想要更改某些元素时，我们使用一个名为 'add(pos, i) 的数组' 表示在 a[pos] 中添加 i：

(k'(x) 是一个函数返回最小的 y >= x 即 k(y) <= x)

    void add(int pos, int i) {
        if (pos <= n) {
            C[pos] += i;
            add(k'(pos), i);
        }
    }

代码的核心也是'skip'。显然C[k'(pos)]是'control segment(C[k(i)..i])'包含C[pos]的最小元素。我们只更新绑定的元素使用 C[pos] 而不是处理所有元素。

现在问题变成了：'找出合适的 k(x) & k'(x) 来完成代码'。k(x) = x-sqrt(n)是一个简单的函数，上面的操作是 O(sqrt(n))。更好的选择是函数 BIT(i)。

BIT(i) 是计算 i 的二进制中的第一个“1”，例如：

    (110100)2 --BIT--> (100)2
    (111)2    --BIT--> (1)2
    (100000)2 --BIT--> (100000)2

一种快速计算 BIT 的方法是使用二元运算符：

    BIT(x) = x & ((~x) + 1)

让我们假设x = (101100)2, ~x = (010011)2, (~x)+1 = (010100)2, x & ((~x) + 1) = (000100)2。它真的有效！(~x)+1使除 BIT(x) 之外的所有位都相反，并且 '&' 清除无用位。

因为 -x = (~x)+1 （看看如何将负整数变成二进制） BIT(x) = x & (-x)

现在我们得到了一个强大的功能。方法我不解释（你自己理解比较好）：

    k(i) = i-BIT(i)+1
    k'(i) = i+BIT(i)

尝试使用 k & k' 来查看上面的代码。

[图表][ http://i.stack.imgur.com/j5z5e.png]

图来自网络

于 2016-08-24T04:35:39.053 回答