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.

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.

Awesome Post :) Very well written !!