BIT：无法理解二进制索引树的更新操作 [英] BIT: Unable to understand update operation in Binary index Tree

问题描述

我刚刚阅读这个问题答案，感到很满意，这是确实是一个梦幻般的回答。它教会了我位的工作。

I have just read answer on this question and was very satisfied and it is indeed a fantastic answer. It taught me the working of BIT.

但最后，倒数第二段是我很努力。它说，

But at the end, the second last paragraph is where I am struggling. It says,

同样，让我们​​想想我们如何做一个更新的一步。去做   这一点，我们将要遵循的访问路径备份根，   更新，我们跟着左上行链路的所有节点。我们可以做的   这种通过实质上做上述算法，但开关全部为1   为0和0至1的。但是，如果我看到的，需要一定的例子，它不   根据我正如通过简单地切换1的和0的工作，

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 ...现在申请，他们先前所给出的步骤，我们最终会更新一些其他的节点左右。

e.g. lets take we want to update value at node 5 = 101 Switching 1s and 0s, we get 010... Now applying the procedure they have given earlier, we will end up updating some other node or so.

我一定要得到它错了。请大家指正。

I must be getting it wrong. Please correct me.

感谢你在前进。

推荐答案

我想你是对的。 使用这样的：

I think you are right. Use this:

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

功能：

INT根（INT node_index）{返回node_index＆GT;＆GT; 1}

INT左（INT node_index）{node_index＆LT;＆LT; 1}

INT权（INT node_index）{左（node_index）| 1}

这篇关于BIT：无法理解二进制索引树的更新操作的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！