我在网上读了2-3本binary indexed tree(又称fenwick树)的教程,但我不明白它到底是做什么的,以及它背后的思想是什么。
我读的教程是
Binary Indexed Trees on TopCoder.com,由boba5551
请帮助我理解BIT

最佳答案

最高编码者的文章不太清楚这是一个可以让你开始的大主意。
bits有助于存储从整数到整数的密集映射f[i],其中i >= 1和您感兴趣的是检索映射域范围内的和,即任意sum_{i = a..b} f[i]a。如果你是用C编写代码的话,这将是:

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

我所说的密度是指大多数bf[i]>0。如果有稀疏映射,则其他数据结构更好。
位使您可以加速此计算,以便总和的运行时间(而不是与i成比例)与b - a成比例插入新元素的时间与此类似。
为此,位存储不同的maplog(b+a),而不是g[k]f[i]的内容是以一种巧妙的方式定义的。
g[k] = sum_{i = k - d + 1 .. k} f[i]

其中gd的值,除最低阶位外所有位都设置为零例如,如果k,则k=8。如果d=8,则k=14等。
注意没有显式树。树是逻辑的,如教程图片所示唯一的存储器是阵列d=2
为什么这是个好主意?事实证明,要找到g,最多只需要对sum_{i = a..b} f[i]2 ceiling(log(b+a))元素进行总结。这些元素可以通过分析ga的二进制1位来确定。详细信息显示在教程中。
最简单的例子:如果您想要b,那么构造一系列索引sum_{i = 1..p} f[i]p_1,…p_2其中p_np_1 = p是通过从p_(i+i)中删除最低1位而形成的。因此p_in的二进制表示中的1个数少1个。现在只要计算一下
sum_{k = p_1, p_2 ... p_n} g[k]

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

09-10 03:52
查看更多