fenwick tree binary indexed tree consider we have an array arr0 n1 we would like to 1 compute the sum of the first i elements 2 modify the value of a specified element of the array arri x where 0 i n1 a simple solution is to run a loop from 0 to i1 and calculate the sum of the elements to update a value simply do arri x the first operation takes on time and the second operation takes o1 time another simple solution is to create an extra array and store the sum of the first ith elements at the ith index in this new array the sum of a given range can now be calculated in o1 time but the update operation takes on time now this works well if there are a large number of query operations but a very few number of update operations there are two solutions that can perform both the query and update operations in ologn time 1 fenwick tree 2 segment tree compared with segment tree binary indexed tree requires less space and is easier to implement returns sum of arr0 index this function assumes that the array is preprocessed and partial sums of array elements are stored in bittree index in bittree is 1 more than the index in arr traverse ancestors of bittreeindex add current element of bittree to sum move index to parent node in getsum view updates a node in binary index tree bittree at given index in bittree the given value val is added to bittreei and all of its ancestors in tree index in bitree is 1 more than the index in arr traverse all ancestors and add val add val to current node of bittree update index to that of parent in update view constructs and returns a binary indexed tree for given array of size n create and initialize bitree as 0 store the actual values in bitree using update returns sum of arr 0 index this function assumes that the array is preprocessed and partial sums of array elements are stored in bit_tree index in bit_tree is 1 more than the index in arr traverse ancestors of bit_tree index add current element of bit_tree to sum move index to parent node in getsum view updates a node in binary index tree bit_tree at given index in bit_tree the given value val is added to bit_tree i and all of its ancestors in tree index in bit_ree is 1 more than the index in arr traverse all ancestors and add val add val to current node of bit_tree update index to that of parent in update view constructs and returns a binary indexed tree for given array of size n create and initialize bit_ree as 0 store the actual values in bit_ree using update
class Fenwick_Tree(object):
    def __init__(self, freq):
        self.arr = freq
        self.n = len(freq)
        
    def get_sum(self, bit_tree, i):
        

        s = 0
      
        
        i = i+1
      
        
        while i > 0: 
      
            
            s += bit_tree[i] 
      
            
            i -= i & (-i) 
        return s 
      
    def update_bit(self, bit_tree, i, v):
        
      
        
        i += 1
      
        
        while i <= self.n: 
      
            
            bit_tree[i] += v 
      
            
            i += i & (-i) 
      
      
    def construct(self):
        
      
        
        bit_tree = [0]*(self.n+1) 
      
        
        for i in range(self.n): 
            self.update_bit(bit_tree, i, self.arr[i]) 

        return bit_tree