We use one extra space because update ( l , r , x ) updates D [ r + 1 ]
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