Fenwick Tree or Binary Indexed Tree

Problem:

Given a array of num, answer what is the sum in range [i, j].

LeetCode 307, 308

If the array is immutable, we can hold an prefix sum array, each position holds the sum from [0, i].

However, if we have many updates to the original array, we need take lot of time to update our prefix sum array, which does not scale very well.

Alternate solution:

• segment tree: worst case space 4n, search 4logn

Solution: Fenwick Tree

• Time Complexity:
  • update, search: $$O(logn)$$
  • build: $$O(nlogn)$$
• Space Complexity: $$O(n)$$
• GeeksForGeeks
• video

Get parent: flip the right most 1 to 0

calculate the range sum [0, i]

1. 2's complement: (binary)complement plus 1
2. AND it with original number

3. subtract from original number

   Example:

   10 = 1010
   1. complement: 0101+1= 0110
   2. 1010 & 0110 = 0010
   2. 1010 - 0010 = 1000 = 8
   

Get Next: to update the value and build the tree

1. 2's complement: (binary)complement plus 1
2. AND it with original number

3. add to original number

   Example:

   1 = 0000001
   1. complement 1111110+1= 11111111
   2. 00000001 & 1111111 = 0000001
   3. 00000001 + 00000001 = 2
   

   2 = 00000010
   1. complement 1111101+1= 11111110
   2. 00000010 & 11111110 = 00000010
   3. 00000010 + 00000010 = 4
   

   Then we add current new value to this position. repeat this process, until the position is larger than the array size.

bit 2D: geeksforgeeks