二进制索引树的概念不太理解 [英] less understanding of binary index tree concept
问题描述
我读2 - 3教程二进制索引树（AKA树状数组）在互联网上，但我不明白它实际上做的，什么是 BIT 背后的理念。
我读的教程
I read 2 - 3 tutorials of binary indexed tree(AKA Fenwick tree) on internet, but I didn't understand what it actually does and what is the idea behind BIT.
The tutorial that I read is
- Binary Indexed Trees on TopCoder.com, By boba5551
请帮助我，使我都懂 BIT 。
推荐答案
顶codeR文章不是那么清楚。这里是可以让你启动的大创意。
The top coder article is not so clear. Here is the big idea that may get you started.
位是良好的存储密集的地图从整数到整数 F [I] ，其中 I＆GT; = 1 和你有兴趣在获取了地图领域，即 sum_ {i = a..b} F [I] 任意的范围总和一个和 B 。如果你的编码在C中，这将是：
BITs are good for storing dense maps from integers to integers f[i], where i >= 1 and you are interested in retrieving sums over ranges of the map domain, i.e. sum_{i = a..b} f[i] for arbitrary a and b. If you were coding in C this would be:
sum = 0; for (i = a; i <= b; i++) sum += f[i];
通过密集的我的意思是 F [I]＆GT; 0 对于大多数我。如果你有一个稀疏的地图，其他的数据结构都比较好。
By dense I mean f[i]>0 for most i. If you have a sparse map, other data structures are better.
位让你加快这一计算，使之和的运行时间 - 而不是正比于 B - A - 是不是成正比日志（B + A）。时间插入一个新元素是相似的。
BITs let you speed up this computation so that the run time of the sum - rather than being proportional to b - a - is instead proportional to log(b+a). Time to insert a new element is similar.
要做到这一点，BIT存储不同的地图政[K] ，而不是 F [I] 。 先按g 的内容在一个巧妙的方式来定义。
To do this, the BIT stores a different map g[k] rather than f[i]. The contents of g are defined in a clever way.
g[k] = sum_{i = k - d + 1 .. k} f[i]
其中， D 是 K 所有，但最低位设置为零的值。例如，如果 K = 8 ，然后 D = 8 。如果 K = 14 ，然后 D = 2 等。
where d is the value of k with all but the lowest order bit set to zero. For example, if k=8, then d=8. If k=14, then d=2, etc.
请注意没有明确的树。树是合乎逻辑的，如图教程图片。唯一的存储阵列先按g 。
Note there is no explicit tree. The tree is logical as shown in the tutorial pictures. The only storage is the array g.
为什么这是一个好主意吗？事实证明，找到 sum_ {i = a..b} F [I] ，你只需要总结至多 2上限（日志（B + A）） 先按g 的元素。这些元素可以通过分析二进制1位 A 和 B 确定。的细节示于教程。
Why is this a good idea? It turns out that to find sum_{i = a..b} f[i], you need only sum up at most 2 ceiling(log(b+a)) elements of g. These elements can be determined by analyzing the binary 1 bits of a and b. The details are shown in the tutorials.
最简单的例子：如果你希望 sum_ {i = 1..p} F [I] ，然后构造了一系列指数 P_1 ， P_2 ... P_N ，其中 P_1 = P 和 P_（I + I）是由 p_i 。因此 N 比1在 P 的二进制再presentation数少一个。现在只需计算
The simplest example: if you want sum_{i = 1..p} f[i], then construct the series of indices p_1, p_2, ... p_n where p_1 = p and p_(i+i) is formed by removing the lowest order 1 bit from p_i. Therefore n is one less than the number of 1's in the binary representation of p. Now just compute
sum_{k = p_1, p_2 ... p_n} g[k]
如果你实践和思考这一点（双关语意），你就会明白为什么它的工作原理。
If you experiment and think about this a bit (pun intended) you'll see why it works.
这篇关于二进制索引树的概念不太理解的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
