algorithm - 对二叉索引树概念了解较少

Question

我在互联网上阅读了 2 - 3 个 binary indexed tree(又名 Fenwick 树)教程，但我不明白它的实际作用以及BIT 背后的想法是什么。我看的教程是

• Binary Indexed Trees on TopCoder.com ，由 boba5551

请帮助我了解BIT。

Answer 1

top coder的文章不是很清楚。以下是可以帮助您入门的好主意。

BIT 适用于存储从整数到整数的密集映射 f[i] , 其中i >= 1并且您有兴趣检索 map 域范围内的总和，即 sum_{i = a..b} f[i]任意 a和 b .如果您使用 C 编写代码，这将是:

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

密集是指 f[i]>0大多数i .如果你有一个稀疏 map ，其他数据结构会更好。

BIT 可让您加快此计算速度，以便总和的运行时间 - 而不是与 b - a 成正比- 相反与 log(b+a) 成正比.插入新元素的时间是相似的。

为此，BIT 存储了一个不同的 map 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 的元素.这些元素可以通过分析a的二进制1位来确定。和 b .详细信息显示在教程中。

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

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

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