与其他数据结构相比，二叉索引树几乎没有或相对没有理论可供研究。唯一简洁地教授它的地方是 topcoder 教程。尽管教程中的所有解释都很完整，但我无法理解这样一棵树背后的直觉是什么？以及如何证明它的正确性？
我认为这个证明很难解释。那么在使用 BIT 时，您遵循什么方法呢？
问问题
12627 次
1 回答
78
我通过@templatetypedef 找到了这个答案，非常清楚地解释了二叉索引树的直觉和证明：答案....
直观地，您可以将二叉索引树视为二叉树的压缩表示，它本身就是标准数组表示的优化。这个答案进入了一个可能的推导。
例如，假设您要存储总共 7 个不同元素的累积频率。您可以从写出将分配数字的七个存储桶开始：
[ ] [ ] [ ] [ ] [ ] [ ] [ ]
1 2 3 4 5 6 7
现在，让我们假设累积频率看起来像这样：
[ 5 ] [ 6 ] [14 ] [25 ] [77 ] [105] [105]
1 2 3 4 5 6 7
使用此版本的数组，您可以通过增加存储在该点的数字的值来增加任何元素的累积频率，然后增加之后所有元素的频率。例如，要将 3 的累积频率增加 7，我们可以将 7 添加到数组中位置 3 处或之后的每个元素，如下所示：
[ 5 ] [ 6 ] [21 ] [32 ] [84 ] [112] [112]
1 2 3 4 5 6 7
这样做的问题是它需要 O(n) 时间来执行此操作，如果 n 很大，这将非常慢。
我们可以考虑改进此操作的一种方法是更改我们存储在存储桶中的内容。您可以考虑仅存储当前频率相对于前一个存储桶增加的数量，而不是将累积频率存储到给定点。例如，在我们的例子中，我们将上面的桶重写如下：
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
现在，我们可以在 O(1) 时间内增加一个桶内的频率，只需将适当的数量添加到该桶中。但是，现在进行查找的总成本变为 O(n)，因为我们必须通过汇总所有较小存储桶中的值来重新计算存储桶中的总数。
我们需要从这里获得二叉索引树的第一个主要见解如下：与其不断地重新计算特定元素之前的数组元素的总和，不如预先计算特定元素之前的所有元素的总和。序列中的点？如果我们能做到这一点，那么我们可以通过将这些预先计算的和的正确组合相加来计算出某个点的累积和。
一种方法是将表示从桶数组更改为节点的二叉树。每个节点都将使用一个值进行注释，该值表示该给定节点左侧所有节点的累积和。例如，假设我们从这些节点构造以下二叉树：
4
/ \
2 6
/ \ / \
1 3 5 7
现在，我们可以通过存储包括该节点及其左子树在内的所有值的累积和来扩充每个节点。例如，给定我们的值，我们将存储以下内容：
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，然后进行正常的二进制搜索，直到找到有问题的节点。当我们这样做时，我们还进行了以下操作：每当我们向右移动时，我们也会将当前值添加到计数器中。
例如，假设我们要查找 3 的总和。为此，我们执行以下操作：
- 从根 (4) 开始。计数器为 0。
- 向左转到节点 (2)。计数器为 0。
- 向右转到节点 (3)。计数器为 0 + 6 = 6。
- 找到节点 (3)。计数器是 6 + 15 = 21。
您也可以想象反向运行此过程：从给定节点开始，将计数器初始化为该节点的值，然后沿着树向上走到根。每当您向上跟随右子链接时，在您到达的节点处添加值。例如，要找到 3 的频率，我们可以执行以下操作：
- 从节点 (3) 开始。计数器是 15。
- 向上到节点 (2)。计数器是 15 + 6 = 21。
- 向上到节点 (1)。计数器是 21。
为了增加一个节点的频率（以及隐式地，它之后的所有节点的频率），我们需要更新树中的节点集，包括该节点在其左子树中。为此，我们执行以下操作：增加该节点的频率，然后开始走到树的根部。每当您点击一个将您作为左孩子的链接时，通过添加当前值来增加您遇到的节点的频率。
例如，要将节点 1 的频率增加 5，我们将执行以下操作：
4
[+32]
/ \
2 6
[ +6] [+80]
/ \ / \
> 1 3 5 7
[ +5] [+15] [+52] [ +0]
从节点 1 开始，将其频率增加 5 得到
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]
我们沿着左子链接向上，所以我们也增加了这个节点的频率：
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]
那是一个左子链接，所以我们也增加这个节点：
4
[+37]
/ \
2 6
[+11] [+80]
/ \ / \
1 3 5 7
[+10] [+15] [+52] [ +0]
现在我们完成了！
最后一步是将其转换为二进制索引树，这就是我们可以用二进制数做一些有趣的事情的地方。让我们用二进制重写这棵树中的每个桶索引：
100
[+37]
/ \
010 110
[+11] [+80]
/ \ / \
001 011 101 111
[+10] [+15] [+52] [ +0]
在这里，我们可以做一个非常非常酷的观察。取出这些二进制数中的任何一个，找到数字中设置的最后一个 1，然后删除该位以及其后的所有位。您现在剩下以下内容：
(empty)
[+37]
/ \
0 1
[+11] [+80]
/ \ / \
00 01 10 11
[+10] [+15] [+52] [ +0]
这是一个非常非常酷的观察：如果您将 0 表示“左”，将 1 表示“右”，则每个数字上的剩余位准确地说明了如何从根开始，然后一直走到那个数字。例如，节点 5 具有二进制模式 101。最后一个 1 是最后一位，因此我们将其删除以得到 10。确实，如果您从根开始，向右 (1)，然后向左 (0)，您结束在节点 5 上！
这很重要的原因是我们的查找和更新操作取决于从节点备份到根的访问路径以及我们是跟随左子链接还是右子链接。例如，在查找期间，我们只关心我们关注的左侧链接。在更新期间，我们只关心我们遵循的正确链接。这个二叉索引树只使用索引中的位就可以非常高效地完成所有这些工作。
关键技巧是这个完美二叉树的以下属性：
给定节点 n，通过取 n 的二进制表示并删除最后一个 1 来给出访问路径上的下一个节点，该节点返回到我们向右走的根。
例如，看一下节点 7 的访问路径，即 111。我们采用的访问路径上涉及到向上跟随右指针的节点是
- 节点 7：111
- 节点 6：110
- 节点 4：100
所有这些都是正确的链接。如果我们取节点 3 的访问路径，即 011，并查看我们向右走的节点，我们得到
- 节点 3：011
- 节点 2：010
- （节点 4：100，跟随左链接）
这意味着我们可以非常非常有效地计算到一个节点的累积和，如下所示：
- 用二进制写出节点 n。
- 将计数器设置为 0。
- 在 n ≠ 0 时重复以下操作：
- 在节点 n 处添加值。
- 从 n 中删除最左边的 1 位。
同样，让我们考虑一下如何进行更新步骤。为此，我们希望沿着访问路径回到根，更新我们沿着左链接向上的所有节点。我们可以通过本质上执行上述算法来做到这一点，但将所有 1 转换为 0 并将 0 转换为 1。
二叉索引树的最后一步是要注意，由于这种按位技巧，我们甚至不需要再显式存储树了。我们可以将所有节点存储在长度为 n 的数组中，然后使用按位旋转技术隐式导航树。事实上，这正是按位索引树所做的——它将节点存储在一个数组中，然后使用这些按位技巧有效地模拟在这棵树中向上行走。
希望这可以帮助！
于 2013-03-16T02:35:55.367 回答