Fenwick Trees

[minaguib]

BTW, to reason a bit about this statement in a simpler fashion: "any natural number “K” can be obtained from sum of other natural numbers (less than K), where these natural numbers are powers of 2"

Think what you're doing mentally when converting a binary number to decimal. For example: 101001

Each one of those 1s represents 2^position, all added together, so:

  41 =   32 (100000 = 2^5)
       +  8 (  1000 = 2^3)
       +  1 (     1 = 2^0)

Since any natural number can be represented in decimal and binary, the rule applies that each binary 1 is the value of 2^that position, all summed up.

[siddcoder]

Hey, thanks for this :)

I tried to be as intuitive as possible in my post, but kind of missed to reason about this one.

Hope you liked the article !!

[jefftchan]

Great post! I found Fenwick trees particularly useful when I was implementing layout / view recycling. The problem is that you need to keep track of a large number of vertically stacked elements with dynamic & varying heights, and you need a way to efficiently get the prefix sum. Would be curious if anyone else has real life use cases of these.

[siddcoder]

Thanks!. I have read that this data structure can be used for range updates and queries. Something that can also be done using Segment Trees. I haven't covered range updates in my article. It only talks about prefix sum and point updates. I will talk about range updates and segment trees in another article soon.

[upjat]

Awesome Post :) Very well written !!