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

Question

我刚刚阅读了关于 this question 的回答并且非常满意，这确实是一个很棒的答案。它教会了我 BIT 的工作。

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

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. But if I see, take some example, it does not work just as by simply switching 1's and 0's, according to me.

例如假设我们要更新节点 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 }