Difference Array | Range update query in O ( 1 ) | Creates a diff array D [ ] for A [ ] and returns it after filling initial values . ; We use one extra space because update ( l , r , x ) updates D [ r + 1 ] ; Does range update ; Prints updated Array ; Note that A [ 0 ] or D [ 0 ] decides values of rest of the elements . ; Array to be updated ; Create and fill difference Array ; After below update ( l , r , x ) , the elements should become 20 , 15 , 20 , 40 ; After below updates , the array should become 30 , 35 , 70 , 60
def initializeDiffArray ( A ) : NEW_LINE INDENT n = len ( A ) NEW_LINE D = [ 0 for i in range ( 0 , n + 1 ) ] NEW_LINE D [ 0 ] = A [ 0 ] ; D [ n ] = 0 NEW_LINE for i in range ( 1 , n ) : NEW_LINE INDENT D [ i ] = A [ i ] - A [ i - 1 ] NEW_LINE DEDENT return D NEW_LINE DEDENT def update ( D , l , r , x ) : NEW_LINE INDENT D [ l ] += x NEW_LINE D [ r + 1 ] -= x NEW_LINE DEDENT def printArray ( A , D ) : NEW_LINE INDENT for i in range ( 0 , len ( A ) ) : NEW_LINE INDENT if ( i == 0 ) : NEW_LINE INDENT A [ i ] = D [ i ] NEW_LINE DEDENT else : NEW_LINE INDENT A [ i ] = D [ i ] + A [ i - 1 ] NEW_LINE DEDENT print ( A [ i ] , end = " ▁ " ) NEW_LINE DEDENT print ( " " ) NEW_LINE DEDENT A = [ 10 , 5 , 20 , 40 ] NEW_LINE D = initializeDiffArray ( A ) NEW_LINE update ( D , 0 , 1 , 10 ) NEW_LINE printArray ( A , D ) NEW_LINE update ( D , 1 , 3 , 20 ) NEW_LINE update ( D , 2 , 2 , 30 ) NEW_LINE printArray ( A , D ) NEW_LINE