Constant time range add operation on an array | Utility method to add value val , to range [ lo , hi ] ; Utility method to get actual array from operation array ; convert array into prefix sum array ; method to print final updated array ; Driver code ; Range add Queries
def add ( arr , N , lo , hi , val ) : NEW_LINE INDENT arr [ lo ] += val NEW_LINE if ( hi != N - 1 ) : NEW_LINE INDENT arr [ hi + 1 ] -= val NEW_LINE DEDENT DEDENT def updateArray ( arr , N ) : NEW_LINE INDENT for i in range ( 1 , N ) : NEW_LINE INDENT arr [ i ] += arr [ i - 1 ] NEW_LINE DEDENT DEDENT def printArr ( arr , N ) : NEW_LINE INDENT updateArray ( arr , N ) NEW_LINE for i in range ( N ) : NEW_LINE INDENT print ( arr [ i ] , end = " ▁ " ) NEW_LINE DEDENT print ( ) NEW_LINE DEDENT N = 6 NEW_LINE arr = [ 0 for i in range ( N ) ] NEW_LINE add ( arr , N , 0 , 2 , 100 ) NEW_LINE add ( arr , N , 1 , 5 , 100 ) NEW_LINE add ( arr , N , 2 , 3 , 100 ) NEW_LINE printArr ( arr , N ) NEW_LINE