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?

up vote 4 down vote accepted

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.

  • Why does i & -i get you to the correct node though? What is so special about removing the least significant bit that it almost magically gets you to the correct node? – 1110101001 Nov 10 '14 at 7:41
  • Note that i -= (i & -i) moves you to the ancestor that is closest to the left side of i. This is the next node you will need if you want to add all the nodes to the left of i. – JS1 Nov 10 '14 at 8:23

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

You can have a look at it here.

I hope it will help.

  • 3
    Please don't just post links as answers, especially when that link could be seen as an attempt to drive traffic to some other website. But posting a summary here with a "For more details see here" link would be great. – David Richerby Feb 19 '15 at 18:47
  • Nonetheless, there is good info here. Thanks for the link. – 1110101001 Feb 21 '15 at 9:06

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.