We use one extra space because update ( l , r , x ) updates D [ r + 1 ]
vector < int > D ( n + 1 ) ; D [ 0 ] = A [ 0 ] , D [ n ] = 0 ; for ( int i = 1 ; i < n ; i ++ ) D [ i ] = A [ i ] - A [ i - 1 ] ; return D ; }