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
function initializeDiffArray ( A ) { let n = A . length ; let D = [ ] ; D [ 0 ] = A [ 0 ] , D [ n ] = 0 ; for ( let i = 1 ; i < n ; i ++ ) D [ i ] = A [ i ] - A [ i - 1 ] ; return D ; } function update ( D , l , r , x ) { D [ l ] += x ; D [ r + 1 ] -= x ; return D ; } function printArray ( A , D ) { for ( let i = 0 ; i < A . length ; i ++ ) { if ( i == 0 ) A [ i ] = D [ i ] ; else A [ i ] = D [ i ] + A [ i - 1 ] ; document . write ( A [ i ] + " " ) ; } document . write ( " " ) ; } let A = [ 10 , 5 , 20 , 40 ] ; let D = initializeDiffArray ( A ) ; D = update ( D , 0 , 1 , 10 ) ; printArray ( A , D ) ; D = update ( D , 1 , 3 , 20 ) ; D = update ( D , 2 , 2 , 30 ) ; printArray ( A , D ) ;