A Fenwick tree or binary indexed tree is a data structure that can efficiently update elements and calculate prefix sums in a table of numbers. This structure was proposed by Peter Fenwick in 1994 to improve the efficiency of arithmetic coding compression algorithms. - Wikipedia

A node in a Fenwick tree has an index and a value. The root's index is 0 and the value is 0. A node's parent is found by clearing the least-significant bit in the index. Given (1-based) sequence, the value of a node is the sum of numbers since the parent's index in the tree. For example, Fenwick tree for the list [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13] can be drawn as follows.

• Root node has index 0₂ and doesn't correspond to any element of the given 1-based sequence.
• Root node has 4 children indices: 1₂, 10₂, 100₂, 1000₂ because removing the least-significant bit in the index of the children gives the root's index, 0₂. However, since the last index of the given 1-based sequence is 13 and 10000₂ is greater, it is not a child index of the root.
• Each node stores a value of the partial sum after the parent's index upto the node's index.
• Node with index 1₂
  • stores the partial sum: 1 = 1
  • leaf node because no other least-significant bit can be added to the index
• Node with index 10₂
  • stores the partial sum: 3 = 1 + 2
  • has a child with index 11₂
• Node with index 100₂
  • stores the partial sum: 10 = 1 + 2 + 3 + 4
  • has 2 children with indices: 101₂, 110₂
• Node with index 1000₂
  • stores the partial sum: 36 = 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8
  • has 3 children with indices: 1001₂, 1010₂, 1100₂
• Node with index 110₂
  • has parent index 100₂ = 4
  • stores the partial sum from index 5 to 6 (=110₂): 11 = 5 + 6

• runs in O(log n) time

• runs in O(log n) time

• runs in O(n) time

• runs in O(n) time

• given a 1-based index, return the index of the parent

def _parent_index(tree_idx):
    """get the parent's index in tree"""
    return tree_idx - _least_significant_bit(tree_idx)

def _least_significant_bit(tree_idx):
    """binary operation to get the least significant bit in a binary index
    because of Python uses a two's complement binary signed integer representation,
    the bits of a binary number and the two's complement only differs in the least
    significant bit.
    
    for example, 
     12 is represented as 00001100
    -12 is represented as 11110100
                        & ________
                   gives  00000100
    which is the least significant bit of 12.
    """
    return tree_idx & -tree_idx

print('12 =', bin(12))
lsb = _least_significant_bit(12)
print('least significant bit:', lsb, '=', bin(lsb))
parent_idx = _parent_index(12)
print('parent index:', parent_idx, '=', bin(parent_idx))
print('least significant bit removed')

12 = 0b1100
least significant bit: 4 = 0b100
parent index: 8 = 0b1000
least significant bit removed