algorithm - BIT:使用二进制索引树？

Question

As it currently stands, this question is not a good fit for our Q&A format. We expect answers to be supported by facts, references, or expertise, but this question will likely solicit debate, arguments, polling, or extended discussion. If you feel that this question can be improved and possibly reopened, visit the help center提供指导。




7年前关闭。




与其他数据结构相比，二进制索引树几乎没有理论要研究。唯一简短地教它的地方 is the topcoder tutorial。尽管本教程的所有解释均已完成，但我无法理解，这棵树背后的直觉是什么？以及如何证明其正确性？

我认为证明很难解释。因此，在使用BIT时，您会采用哪种方法？

最佳答案

我发现@templatetypedef的this answer非常清楚地解释了二进制索引树的直觉和证明:
答案....

直观地，您可以将二进制索引树视为二进制树的压缩表示形式，它本身是对标准数组表示形式的优化。这个答案有一个可能的推论。

例如，假设您要存储总共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]

在这里，我们可以做一个非常非常酷的观察。取这些二进制数字中的任何一个，找到该数字中设置的最后一个1，然后将该位及其后的所有位都删除。现在，您剩下以下内容:

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

这是一个非常非常酷的观察结果:如果将0表示“左”，将1表示“右”，则每个数字上的其余位将准确说明如何从根开始，然后向下移动到该数字。例如，节点5具有二进制模式101。最后1是最后一位，因此我们将其丢弃以得到10。实际上，如果您从根开始，请向右(1)，然后向左(0)，然后结束在节点5上!

之所以如此重要，是因为我们的查找和更新操作取决于从节点备份到根节点的访问路径，以及我们是否遵循左或右子链接。例如，在查找期间，我们只关心我们遵循的左侧链接。在更新期间，我们只关心我们遵循的正确链接。仅通过使用索引中的位，该二进制索引树就可以高效地完成所有这些工作。

关键技巧是此完美的二叉树的以下属性:

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。我们访问根的访问路径上涉及向上跟随右指针的节点是

节点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的数组中，然后使用按位旋转技术来隐式导航树。实际上，这正是按位索引的树所做的工作-将节点存储在数组中，然后使用这些按位技巧来有效地模拟在此树中的向上行走。

希望这可以帮助!

关于algorithm - BIT:使用二进制索引树？ ，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/15439233/

上一篇：java - 什么是NullPointerException，我该如何解决？

下一篇：swift - 如何在 WKWebView 中捕获通知？

相关文章：

c - 完美平衡二叉搜索树

algorithm - 使数组严格递增所需的最少更改

language-agnostic - 集成测试 - "no exceptions are thrown"方法。是否有意义？

python - 你如何制作一个模拟二维网格的邻接矩阵

javascript - 在 d3js 树中的标签后添加图形

java - 选择 SWT.Tree 中的 SWT.TreeItem

c++ - 我的回溯代码中的错误 - Bridge Crossing

algorithm - 实现迭代单栈二叉树复制函数

language-agnostic - "program to an interface"是什么意思？

algorithm - 尝试检查树是否是最大堆

Answer 1

我发现@templatetypedef的this answer非常清楚地解释了二进制索引树的直觉和证明:
答案....

直观地，您可以将二进制索引树视为二进制树的压缩表示形式，它本身是对标准数组表示形式的优化。这个答案有一个可能的推论。

例如，假设您要存储总共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]

在这里，我们可以做一个非常非常酷的观察。取这些二进制数字中的任何一个，找到该数字中设置的最后一个1，然后将该位及其后的所有位都删除。现在，您剩下以下内容:

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

这是一个非常非常酷的观察结果:如果将0表示“左”，将1表示“右”，则每个数字上的其余位将准确说明如何从根开始，然后向下移动到该数字。例如，节点5具有二进制模式101。最后1是最后一位，因此我们将其丢弃以得到10。实际上，如果您从根开始，请向右(1)，然后向左(0)，然后结束在节点5上!

之所以如此重要，是因为我们的查找和更新操作取决于从节点备份到根节点的访问路径，以及我们是否遵循左或右子链接。例如，在查找期间，我们只关心我们遵循的左侧链接。在更新期间，我们只关心我们遵循的正确链接。仅通过使用索引中的位，该二进制索引树就可以高效地完成所有这些工作。

关键技巧是此完美的二叉树的以下属性:

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。我们访问根的访问路径上涉及向上跟随右指针的节点是

节点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的数组中，然后使用按位旋转技术来隐式导航树。实际上，这正是按位索引的树所做的工作-将节点存储在数组中，然后使用这些按位技巧来有效地模拟在此树中的向上行走。

希望这可以帮助!