mshereef's blog

Why do point updates work in a Fenwick Tree (Binary Indexed Tree) ?
By mshereef, history, 3 years ago, In English

I recently learnt about the Fenwick Tree data structure and i understand how everything works and how it is implemented.

Now my issue is in the point update algorithm:

I understand why adding the LSB to a number would get us the next number with a range that also contains/covers the current number we are on. This is because adding any number less than the LSB won’t work, as well as a number with the same LSB can not cover our current number either (Proof in this article). Therefore the only possible option left is a number with a greater LSB, and to get the smallest such number this can be done by adding the LSB to the current number, and I understand why this number will always cover the previous number we were on.

Now what I can’t see is why adding the LSB again to the number we moved on to would also get us the next range that we need to update. I tried reading this article with the same question but I could not find any useful answer.

If anyone can help me with this I would really appreciate it because personally it doesn’t feel right using something without understanding why it works.

Thank you in advance.

  • Vote: I like it
  • +7
  • Vote: I do not like it

»
3 years ago, # |
← Rev. 7   Vote: I like it 0 Vote: I do not like it

Consider the original number as XXXXXXX1000 where X can be anything 0 or 1. Now I need to add the smallest number such that the new number is greater than original number and removal of LSB from new number gives a strictly smaller number than original number. You know that LSB works for the first time, after adding LSB, your new number must look like this: XXXXX100000, here note that the prefix (XXXXX) of the new number remain unchanged (it is exactly equal to the bits of orignal number) (and that's the most important because that's the reason why removal of LSB from new number results in lesser than orginal number). Now can u add less than LSB to the new number? XXXXX101000? Nope. Can u add LSB? (Remember we gotta add smallest possible number every time) yes! Because again adding LSB will form a number like this XX100000000 (here X is unchanged) and removal of LSB will form XX000000000 which is smaller than XXXXXXX1000. The property that few leading bit remaining unchanged after adding LSB plays the key role.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks a lot, I never thought about "The property that few leading bit remaining unchanged after adding LSB". I think I finally get it now.

    → Reply