3. Fenwick Tree #

Created Tuesday 28 July 2020

@ToBeDone

• Also called Binary Index Tree(BIT)
• Used for range queries and updates.
• Segment trees are used for the same.
• Why this:
  1. Code is easy and short.
  2. Takes less space, n+1 instead of 4n

How is the array built?

• Index starts from 1. This is why there are n+1 nodes, index 0 is a dummy node.
• 1 → 2^0^+0, 2 = 2^1^+0, 3 = 2^1^+1, 4 = 2^2^+0, 5=2^2^+2^0 ^⇒ i.e abcdefghi = binary representation.