BIT: Unable to understand update operation in Binary index Tree

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.

Answer 1

If you don't stick to the claim of "switching all 1's to 0's and 0's to 1's" (I am also confused) in that post, here is the simple bitwise trick for updating used in the original paper "A New Data Structure for Cumulative Frequency Tables" (Figure 5) by Peter Fenwick (Ix for index).

Repeat:
Tree[Ix] := Tree[Ix] + val;
Ix := Ix + BitAnd(Ix, -Ix);    // add the least-significant one
Until Ix >= TableSize

---

That is, the nodes accessed via a left link upward from the original node i can be calculated by
i += i && -i.

i && -i is the least significant bit of i. i += i && -i moves you to the ancestor that is closest to the right side of i. This is the next node you will need if you want to add all the nodes to the right of i.

In your example, i = 5_(10) = 101_(2). The first i && -i gives 001 and i + i && -i moves you to node i' = 110_(2) = 6_(10). The second i' && -i' on i' gives 010 and i' + i' && i' moves you to node i'' = 1000_(2) (which is too large).

For an example with 31 nodes and i = 9 = 1001, you will access the following nodes: i' = 1001 + 0001 = 1010, i'' = 1010 + 0010 = 1100, and i''' = 1100 + 0100 = 10000 (which is too large).

---

By the way, in the case of query, the bitwise trick is simply modified to i -= i && -i. It is easy to verify that this trick agrees with the procedure of "Clearing the rightmost 1 bit". Also see the related post here.

Answer 2

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.

Answer 3

In BIT query, the trick is removing the last 1 bit.

In BIT update is adding the last 1 bit.

• Write out node n in binary.
• Set the counter to 0.
• Repeat the following while n <= N (the largest value in BIT):
  • Add in the value at node n.
  • Get the rightmost 1 bit from n, and adding it to n.

In languages supporting bit operation, it can be simply archived by $n \leftarrow n+(n\&(-n))$

Take 11 for example: (suppose full range is 1~32) $$11=1011_2 \to 1011_2+1_2=1100_2$$ $$\to 1100_2+100_2=10000_2$$ $$\to 10000_2+10000_2=100000_2=32$$. So the path is $11\to12\to16\to32$