BIT：无法理解二进制索引树中的更新操作

Question

我刚刚阅读了this question上的答案，非常满意，它确实是一个绝佳的答案。它教会了我BIT的工作。

但最后，第二个最后一段是我挣扎的地方。它说，

同样，让我们​​考虑如何做一个更新步骤。要做 这一点，我们希望按照访问路径备份到根目录， 更新我们沿着左侧链接向上的所有节点。我们可以做 这基本上是通过上述算法，但切换所有1的 为0和0的1。但是，如果我看到，举个例子，它不会像 那样工作，就像我简单地切换1和0一样。

例如，让我们想要在节点5 = 101处更新值。切换1和0，我们得到010 ...现在应用他们之前给出的过程，我们将最终更新其他节点。

我一定是弄错了。请纠正我。

预先感谢您。

Answer 1

我认为你是对的。 使用此：

     1 
      /   \ 
     2      3 
    / \    / \ 
    4   5   6   7 
/ \  / \  / \  /\ 
8  9 10 11 12 13 14 15 

功能：

int root(int node_index) { return node_index >> 1 }

int left(int node_index) { node_index << 1 }

int right(int node_index) { left(node_index) | 1 }