我在网上读了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];
我所说的密度是指大多数
b
的f[i]>0
。如果有稀疏映射,则其他数据结构更好。位使您可以加速此计算,以便总和的运行时间(而不是与
i
成比例)与b - a
成比例插入新元素的时间与此类似。为此,位存储不同的map
log(b+a)
,而不是g[k]
。f[i]
的内容是以一种巧妙的方式定义的。g[k] = sum_{i = k - d + 1 .. k} f[i]
其中
g
是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)
中删除最低1位而形成的。因此p_i
比n
的二进制表示中的1个数少1个。现在只要计算一下sum_{k = p_1, p_2 ... p_n} g[k]
如果你尝试一下并稍微考虑一下(双关语的意思),你就会明白它为什么有效。