I have just read this answer and was very satisfied and it is indeed a fantastic

Question

I have just read this answer 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,

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.

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.

Thank you in advance.

Explanation / Answer

I believe you should be switching the 1s and 0s in the algorithm, not the number itself. In other words:

Given node n, the next node on the access path back up to the root in which we go left is given by taking the binary representation of n and removing the last 0.

So the algorithm for updating becomes:

Write out node n in binary.
Repeat the following while n ? 0:
Add your value to node n.
"Remove" the rightmost '0' bit from n.

But I'm not quite sure what "remove" means here. In the original case it just means 0:ing the bit, but that doesn't work here.

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.