Binary Indexed Trees: Why does i & -i work?

Question

I already read this related question on the intuition behind binary indexed trees, and while the answer explains how the tree structure works, it does not really explain how this correlates back to the array representation where the next node is accessed based on the current nodes index according to $i \mathrel{\&} -i$.

I know physically that $i \mathrel{\&} -i$ gives you the highest power of 2 that divides $i$, essentially the least significant set of bits, but I don't see why adding or subtracting this to/from the current index allows you to jump around to get to the wanted node.

Linking this back to the tree representation,

      4
   /     \
  2       6
 / \     / \
1   3   5   7

I see how the left parent of a node with index N is $(N - 2^h)$ and the right parent is $(N + 2^h)$ where h is the height of the subtree from N down (including N), and this seems to be related to why the $i \mathrel{\&} -i$ works.

However, what about the cases like finding the previous node of 5, which according to $5 - 5\mathrel{\&}-5$ is 4? The formula $N - 2^h$ also seems to work except there is no direct link between 4 and 5. How do you prove that it works in these cases too?

Answer 1

Assuming that your tree is storing cumulative sums, one query you would like to make is "what is the cumulative sum to index n". Suppose the tree is as shown in the OP, and n is 5. The answer to the question would be found by adding the sum in node 4 and the sum in node 5. This is because each node is storing the cumulative sum of itself plus its left subtree (if any). Thus, node 4 has the cumulative sum of indices 1-4 and node 5 has the cumulative sum of index 5 (just itself). Because of the way the tree is built, you basically need to visit one node for each 1 bit in the binary representation of your index.

So the algorithm to compute the cumulative sum is to start at the given index, in this case 5. Note that 5 is 101 in binary. Add its sum to the total. Then, to get to the next node needed, we want to remove the least significant bit (we want to get from 101 to 100). The least significant bit of i is i & -i. To remove the least significant bit, i -= (i & -i). That gets us to node 4. We add node 4's sum to the total. Then we remove the next significant bit, leaving 0 which means we are at the end.

If the tree were bigger, and the starting index were 50 (which is 110010 in binary), we'd have to visit node 50 (110010), node 48 (110000), and node 32 (100000). In this example, node 32 contains the sums of 1-32, node 48 has the sums of 33-48, and node 50 has the sums of 49-50.

Answer 2

I have recently written a detailed post about Binary Indexed Tree.

You can have a look at it here.

I hope it will help.