BIT:使用二进制索引树？

Question

与其他数据结构相比,二进制索引树具有非常少或相对没有理论可供研究.顶级编码器教程是唯一能够简洁教授它的地方.虽然教程在所有解释中都是完整的,但我无法理解这种树背后的直觉是什么？以及如何证明它的正确性？

我认为证明是复杂的解释.那么在使用BIT时,您遵循什么方法？

Answer 1

我发现@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,我们可以在位置3处或之后的数组中为每个元素添加7,如下所示:

[ 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]

在这里,我们可以做一个非常非常酷的观察.获取这些二进制数中的任何一个,找到数字中设置的最后一个,然后关闭该位以及它之后的所有位.您现在离开以下内容:

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

这是一个非常非常酷的观察结果:如果你将0表示为"左"而1表示"正确",则每个数字上的其余位将确切地说明如何从根开始,然后向下走到该数字.例如,节点5具有二进制模式101.最后一个是最后一位,所以我们将其删除为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的数组中,然后使用按位的twiddling技术隐式地导航树.事实上,这正是按位索引树所做的 - 它将节点存储在一个数组中,然后使用这些按位技巧有效地模拟在这棵树中向上行走.

希望这可以帮助!