一个二进制索引树有很少或比较没有理论研究相对于其他的数据结构。在那里教简洁唯一的地方是顶级codeR教程。虽然教程完成在所有的解释，我不明白这背后是什么这样的树的直觉？而如何证明它的正确性？

A binary indexed tree has very few or relatively no theory to study as compared to other data structures. The only place where it is taught succinctly is the topcoder tutorial. Although the tutorial is complete in all the explanations, I cannot understand that what is the intuition behind such a tree? And how to prove it's correctness?

我presume的证明是复杂的解释。因此，使用位当，你遵循什么方法？

I presume that the proof is to complex to explain. So when using BIT, what approach do you follow?

推荐答案

我发现this回答通过@templatetypedef非常清楚地解释有关的二进制索引树的直觉和证明： 答案......

I found this answer by @templatetypedef very clearly explain about the intuition and proof of a binary indexed tree: The answer....

直观地说，你可以把一个二进制索引树作为一个COM pressed重新$ P $二叉树本身就是一个标准的阵列重新presentation的优化psentation的。这个答案将进入一个可能的推导。

Intuitively, you can think of a binary indexed tree as a compressed representation of a binary tree that is itself an optimization of a standard array representation. This answer goes into one possible derivation.

让我们假设，例如，要存储累积频率，共7种不同的元素。你可以通过编写了七斗到其中的数字将被分发开始：

Let's suppose, for example, that you want to store cumulative frequencies for a total of 7 different elements. You could start off by writing out seven buckets into which the numbers will be distributed:

[   ] [   ] [   ] [   ] [   ] [   ] [   ]
  1     2     3     4     5     6     7

现在，让我们假设的累积频率是这个样子：

Now, let's suppose that the cumulative frequencies look something like this:

[ 5 ] [ 6 ] [14 ] [25 ] [77 ] [105] [105]
  1     2     3     4     5     6     7

使用此版本的阵列，则可以通过增加存储在该点的数量的值，则递增一切的附带事后频率递增的任何元件的累积频率。例如，为了增加3的累积频率由7，我们可以在或后3位阵列中添加7至每个元件，如下所示：

Using this version of the array, you can increment the cumulative frequency of any element by increasing the value of the number stored at that spot, then incrementing the frequencies of everything that come afterwards. For example, to increase the cumulative frequency of 3 by 7, we could add 7 to each element in the array at or after position 3, as shown here:

[ 5 ] [ 6 ] [21 ] [32 ] [84 ] [112] [112]
  1     2     3     4     5     6     7

这里的问题是，它需要O（n）的时间来做到这一点，这是pretty的很慢，如果n很大。

The problem with this is that it takes O(n) time to do this, which is pretty slow if n is large.

这是我们可以考虑提高该操作将是改变我们存储在桶的一种方式。而不是存储累积频率达到给定的点，而是可以认为只是存储当前的频率相对增加到previous斗量。例如，在我们的例子中，我们可以把上面的水桶如下：

One way that we can think about improving this operation would be to change what we store in the buckets. Rather than storing the cumulative frequency up to the given point, you can instead think of just storing the amount that the current frequency has increased relative to the previous bucket. For example, in our case, we would rewrite the above buckets as follows:

Before:
[ 5 ] [ 6 ] [21 ] [32 ] [84 ] [112] [112]
  1     2     3     4     5     6     7

After:
[ +5] [ +1] [+15] [+11] [+52] [+28] [ +0]
  1     2     3     4     5     6     7

现在，我们可以（1）只需添加适量的桶增加一个水桶内的频率，时间为O。然而，做一个查询的总成本，现在变成了O（n）的，因为我们要在所有的小水桶总结值总在斗重新计算。

Now, we can increment the frequency within a bucket in time O(1) by just adding the appropriate amount to that bucket. However, the total cost of doing a lookup now becomes O(n), since we have to recompute the total in the bucket by summing up the values in all smaller buckets.

我们需要从这里到二进制索引树来获得的第一个主要观点是如下：而不是不断地重新计算数组元素precede一个特定的元素，如果我们要precompute总和序列中的特定点之前的所有元素的总和？如果我们能做到这一点，那么我们就可以计算出的累加和在一个点上仅通过总结这些precomputed款项的正确组合。

The first major insight we need to get from here to a binary indexed tree is the following: rather than continuously recomputing the sum of the array elements that precede a particular element, what if we were to precompute the total sum of all the elements before specific points in the sequence? If we could do that, then we could figure out the cumulative sum at a point by just summing up the right combination of these precomputed sums.

要做到这一点的方法之一是从被水桶的阵列改变重新presentation到作为节点的二进制树。每个节点将被注解为一个值，该重新presents所有节点的累积总和到该给定节点的左侧。例如，假设我们从这些节点构造如下二叉树：

One way to do this is to change the representation from being an array of buckets to being a binary tree of nodes. Each node will be annotated with a value that represents the cumulative sum of all the nodes to the left of that given node. For example, suppose we construct the following binary tree from these nodes:

             4
          /     \
         2       6
        / \     / \
       1   3   5   7

现在，我们可以通过存储所有的值，包括该节点和它的左子树的累计总和增大每个节点。例如，假定我们的价值观，我们将存储以下内容：

Now, we can augment each node by storing the cumulative sum of all the values including that node and its left subtree. For example, given our values, we would store the following:

Before:
[ +5] [ +1] [+15] [+11] [+52] [+28] [ +0]
  1     2     3     4     5     6     7

After:
                 4
               [+32]
              /     \
           2           6
         [ +6]       [+80]
         /   \       /   \
        1     3     5     7
      [ +5] [+15] [+52] [ +0]

鉴于这种树状结构，可以很容易地确定累计总和到一个点。我们的想法是这样的：我们维持一个计数器，最初为0，然后做一个正常的二进制搜索，直到发现有问题的节点。当我们这样做，我们也如下：。我们将正确的任何时候，我们还可以添加在当前值计数器

Given this tree structure, it's easy to determine the cumulative sum up to a point. The idea is the following: we maintain a counter, initially 0, then do a normal binary search up until we find the node in question. As we do so, we also the following: any time that we move right, we also add in the current value to the counter.

例如，假设我们要查找的总和为3。要做到这一点，我们做到以下几点：

For example, suppose we want to look up the sum for 3. To do so, we do the following:

从根开始（4）。计数器为0。 往左到节点（2）。计数器为0。 转到正确的节点（3）。计数器为0 + 6 = 6。 找到节点（3）。计数器为6 + 15 = 21。

您也可以想像反向运行此过程：开始在一个给定的节点，初始化计数器到该节点的值，然后步行树的根。你跟着一个右子链接向上任何时候，在您来到该节点的值增加。例如，要查找频率3，我们可以做到以下几点：

You could imagine also running this process in reverse: starting at a given node, initialize the counter to that node's value, then walk up the tree to the root. Any time you follow a right child link upward, add in the value at the node you arrive at. For example, to find the frequency for 3, we could do the following:

启动节点（3）。计数器为15。 转到向上节点（2）。计数器是15 + 6 = 21。 转到向上节点（1）。计数器为21。

要增加一个节点（以及隐含，而来后它的所有节点的频率），我们需要更新组包括在其左子树节点树中的节点的频率。要做到这一点，我们做到以下几点：增加的频率，该节点，然后开始步行到树的根。你跟着一个链接，带你作为一个左孩子的任何时间，由目前的增值增加你遇到的节点的频率。

To increment the frequency of a node (and, implicitly, the frequencies of all nodes that come after it), we need to update the set of nodes in the tree that include that node in its left subtree. To do this, we do the following: increment the frequency for that node, then start walking up to the root of the tree. Any time you follow a link that takes you up as a left child, increment the frequency of the node you encounter by adding in the current value.

例如，以五点加1的频率，我们可以做到以下几点：

For example, to increment the frequency of node 1 by five, we would do the following:

                 4
               [+32]
              /     \
           2           6
         [ +6]       [+80]
         /   \       /   \
      > 1     3     5     7
      [ +5] [+15] [+52] [ +0]

开始在节点1，由5增加它的频率要获得

Starting at node 1, increment its frequency by 5 to get

                 4
               [+32]
              /     \
           2           6
         [ +6]       [+80]
         /   \       /   \
      > 1     3     5     7
      [+10] [+15] [+52] [ +0]

现在，去其母公司：

                 4
               [+32]
              /     \
         > 2           6
         [ +6]       [+80]
         /   \       /   \
        1     3     5     7
      [+10] [+15] [+52] [ +0]

我们遵循左子链接向上，所以我们增加这个节点的频率和：

We followed a left child link upward, so we increment this node's frequency as well:

                 4
               [+32]
              /     \
         > 2           6
         [+11]       [+80]
         /   \       /   \
        1     3     5     7
      [+10] [+15] [+52] [ +0]

我们现在去到它的父：

               > 4
               [+32]
              /     \
           2           6
         [+11]       [+80]
         /   \       /   \
        1     3     5     7
      [+10] [+15] [+52] [ +0]

这是一个左子链接，所以我们增加这个节点，以及：

That was a left child link, so we increment this node as well:

                 4
               [+37]
              /     \
           2           6
         [+11]       [+80]
         /   \       /   \
        1     3     5     7
      [+10] [+15] [+52] [ +0]

现在，我们就大功告成了！

And now we're done!

最后一步是从这个转换为二进制索引树，这是我们可以做一些有趣的事情二进制数。让我们重新编写每个桶指数在此树以二进制：

The final step is to convert from this to a binary indexed tree, and this is where we get to do some fun things with binary numbers. Let's rewrite each bucket index in this tree in binary:

                100
               [+37]
              /     \
          010         110
         [+11]       [+80]
         /   \       /   \
       001   011   101   111
      [+10] [+15] [+52] [ +0]

在这里，我们可以做一个非常，非常冷静的观察。采取任何这些二进制数，发现被设置在数字的最后1，然后删除该位关闭，以及所有来后，它的位。您现在只剩下以下内容：

Here, we can make a very, very cool observation. Take any of these binary numbers and find the very last 1 that was set in the number, then drop that bit off, along with all the bits that come after it. You are now left with the following:

              (empty)
               [+37]
              /     \
           0           1
         [+11]       [+80]
         /   \       /   \
        00   01     10   11
      [+10] [+15] [+52] [ +0]

下面是一个非常，非常冷静的观察：如果你把0的意思是左和1的意思是正确的，每个号码的其余位拼出究竟是如何从根开始，然后步行到这数。例如，节点5具有二元模式101.最后1是最后一点，所以我们放弃了得到10的确，如果从根开始，向右走（1），然后向左走（0），则结束达节点5！

Here is a really, really cool observation: if you treat 0 to mean "left" and 1 to mean "right," the remaining bits on each number spell out exactly how to start at the root and then walk down to that number. For example, node 5 has binary pattern 101. The last 1 is the final bit, so we drop that to get 10. Indeed, if you start at the root, go right (1), then go left (0), you end up at node 5!

的原因，这是显著的是，我们的查找和更新操作依赖的访问路径上从节点备份到根和我们是否以下左或右子链接。例如，在查找过程中，我们只关心我们遵循左侧链接。在更新过程中，我们只关心我们按照正确的链接。这种二进制树索引仅仅使用索引中的位有效地做这一切的超级。

The reason that this is significant is that our lookup and update operations depend on the access path from the node back up to the root and whether we're following left or right child links. For example, during a lookup, we just care about the left links we follow. During an update, we just care about the right links we follow. This binary indexed tree does all of this super efficiently by just using the bits in the index.

关键的技巧是这个完美的二叉树的下列财产：

The key trick is the following property of this perfect binary tree:

由于节点n，下一个节点的访问路径上的备份根中，我们去的权利是通过取n的二进制再presentation和取出最后1中给出。

Given node n, the next node on the access path back up to the root in which we go right is given by taking the binary representation of n and removing the last 1.

例如，看一看的访问路径为节点7，这是111的访问路径，我们拿根上的节点涉及以下内容的右指针向上为

For example, take a look at the access path for node 7, which is 111. The nodes on the access path to the root that we take that involve following a right pointer upward is

节点7：111 节点6：110 节点4：100

所有这些都是正确的链接。如果我们把节点3，这是011的访问路径，并看看我们去正确的节点，我们得到

All of these are right links. If we take the access path for node 3, which is 011, and look at the nodes where we go right, we get

节点3：011 节点2：010 的（节点4：100，这是继左链接）的

这意味着我们可以非常有效地计算累计金额达节点如下：

This means that we can very, very efficiently compute the cumulative sum up to a node as follows:

写出节点n的二进制文件。 设置计数器为0。 重复以下，而N'NE; 0： 添加在节点n的值。 删除从n最左边的1位。 Write out node n in binary. Set the counter to 0. Repeat the following while n ≠ 0: Add in the value at node n. Remove the leftmost 1 bit from n.

同样，让我们​​想想我们如何做一个更新的一步。要做到这一点，我们要遵循的访问路径备份根，更新我们跟着左上行链路的所有节点。我们可以通过实质上执行上述算法，但切换全部为1至0和0至1的做到这一点。

Similarly, let's think about how we would do an update step. To do this, we would want to follow the access path back up to the root, updating all nodes where we followed a left link upward. We can do this by essentially doing the above algorithm, but switching all 1's to 0's and 0's to 1's.

在二进制索引树的最后一步是要注意，因为这种按位诡计，我们甚至不需要有树明确地存储了。我们可以只存储所有的节点长度为n的数组，然后用按位玩弄技巧隐式导航树。事实上，这正是按位索引树那样 - 它存储在一个数组中的节点，然后使用这些按位技巧，以有效地模拟这种树向上走。

The final step in the binary indexed tree is to note that because of this bitwise trickery, we don't even need to have the tree stored explicitly anymore. We can just store all the nodes in an array of length n, then use the bitwise twiddling techniques to navigate the tree implicitly. In fact, that's exactly what the bitwise indexed tree does - it stores the nodes in an array, then uses these bitwise tricks to efficiently simulate walking upward in this tree.

希望这有助于！