dev*_*sda 3 language-agnostic algorithm tree data-structures
我在互联网上阅读了2 - 3个二进制索引树(AKA Fenwick树)的教程,但我不明白它实际上做了什么以及背后的想法是什么BIT.我读的教程是
请帮我让我明白BIT.
顶级编码器文章不太清楚.这是一个可以帮助您入门的重要创意.
BIT适用于存储从整数到整数的密集映射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]
如果你试验并考虑一下(双关语),你会明白为什么它有效.