Binary Indexed Tree : Range Updates and Point Queries | Updates a node in Binary Index Tree ( BITree ) at given index in BITree . The given value ' val ' is added to BITree [ i ] 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 BI 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 BITree [ ] as 0 ; Store the actual values in BITree [ ] using update ( ) ; SERVES THE PURPOSE OF getElement ( ) Returns sum of arr [ 0. . index ] . This function assumes that the array is preprocessed and partial sums of array elements are stored in BITree [ ] ; Iniialize result ; index in BITree [ ] is 1 more than the index in arr [ ] ; Traverse ancestors of BITree [ index ] ; Add current element of BITree to sum ; Move index to parent node in getSum View ; Return the sum ; Updates such that getElement ( ) gets an increased value when queried from l to r . ; Increase value at ' l ' by 'val   ; Decrease value at ' r + 1' by 'val   ; Driver code ; Add 2 to all the element from [ 2 , 4 ] ; Find the element at Index 4 ; Add 2 to all the element from [ 0 , 3 ] ; Find the element at Index 3
def updateBIT ( BITree , n , index , val ) : NEW_LINE INDENT index = index + 1 NEW_LINE while ( index <= n ) : NEW_LINE INDENT BITree [ index ] += val NEW_LINE index += index & ( - index ) NEW_LINE DEDENT DEDENT def constructBITree ( arr , n ) : NEW_LINE INDENT BITree = [ 0 ] * ( n + 1 ) NEW_LINE for i in range ( n ) : NEW_LINE INDENT updateBIT ( BITree , n , i , arr [ i ] ) NEW_LINE DEDENT return BITree NEW_LINE DEDENT def getSum ( BITree , index ) : NEW_LINE INDENT sum = 0 NEW_LINE index = index + 1 NEW_LINE while ( index > 0 ) : NEW_LINE INDENT sum += BITree [ index ] NEW_LINE index -= index & ( - index ) NEW_LINE DEDENT return sum NEW_LINE DEDENT def update ( BITree , l , r , n , val ) : NEW_LINE INDENT updateBIT ( BITree , n , l , val ) NEW_LINE updateBIT ( BITree , n , r + 1 , - val ) NEW_LINE DEDENT arr = [ 0 , 0 , 0 , 0 , 0 ] NEW_LINE n = len ( arr ) NEW_LINE BITree = constructBITree ( arr , n ) NEW_LINE l = 2 NEW_LINE r = 4 NEW_LINE val = 2 NEW_LINE update ( BITree , l , r , n , val ) NEW_LINE index = 4 NEW_LINE print ( " Element ▁ at ▁ index " , index , " is " , getSum ( BITree , index ) ) NEW_LINE l = 0 NEW_LINE r = 3 NEW_LINE val = 4 NEW_LINE update ( BITree , l , r , n , val ) NEW_LINE index = 3 NEW_LINE print ( " Element ▁ at ▁ index " , index , " is " , getSum ( BITree , index ) ) NEW_LINE