BIT: Unable to understand update operation in Binary index Tree
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 &gt;= TableSize




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

i &amp;&amp; -i is the least significant bit of i. i += i &amp;&amp; -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 &amp;&amp; -i gives 001 and i + i &amp;&amp; -i moves you to node i' = 110_(2) = 6_(10). The second i' &amp;&amp; -i' on i' gives 010 and i' + i' &amp;&amp; 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 &amp;&amp; -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.