Queries to calculate sum by alternating signs of array elements in a given range | Function to build the segment tree ; If current node is a leaf node of the segment tree ; Update tree [ index ] ; Update tree [ index ] ; Divide the segment tree ; Update on L segment tree ; Update on R segment tree ; Find the sum from L subtree and R subtree ; Function to update elements at index pos by val in the segment tree ; If current node is a leaf node ; If current index is even ; Update tree [ index ] ; Update tree [ index ] ; Divide the segment tree elements into L and R subtree ; If element lies in L subtree ; Update tree [ index ] ; Function to find the sum of array elements in the range [ L , R ] ; If start and end not lies in the range [ L , R ] ; If start and end comleately lies in the range [ L , R ] ; Stores sum from left subtree ; Stores sum from right subtree ; Driver Code
function build ( tree , arr , start , end , index ) { if ( start == end ) { if ( start % 2 == 0 ) { tree [ index ] = arr [ start ] ; } else { tree [ index ] = - arr [ start ] ; } return ; } var mid = start + parseInt ( ( end - start ) / 2 ) ; build ( tree , arr , start , mid , 2 * index + 1 ) ; build ( tree , arr , mid + 1 , end , 2 * index + 2 ) ; tree [ index ] = tree [ 2 * index + 1 ] + tree [ 2 * index + 2 ] ; } function update ( tree , index , start , end , pos , val ) { if ( start == end ) { if ( start % 2 == 0 ) { tree [ index ] = val ; } else { tree [ index ] = - val ; } return ; } var mid = start + parseInt ( ( end - start ) / 2 ) ; if ( mid >= pos ) { update ( tree , 2 * index + 1 , start , mid , pos , val ) ; } else { update ( tree , 2 * index + 2 , mid + 1 , end , pos , val ) ; } tree [ index ] = tree [ 2 * index + 1 ] + tree [ 2 * index + 2 ] ; } function FindSum ( tree , start , end , L , R , index ) { if ( L > end R < start ) { return 0 ; } if ( L <= start && R >= end ) { return tree [ index ] ; } var mid = start + parseInt ( ( end - start ) / 2 ) ; var X = FindSum ( tree , start , mid , L , R , 2 * index + 1 ) ; var Y = FindSum ( tree , mid + 1 , end , L , R , 2 * index + 2 ) ; return X + Y ; } var arr = [ 1 , 2 , 3 , 4 ] ; var N = arr . length ; var tree = Array ( 4 * N + 5 ) . fill ( 0 ) ; build ( tree , arr , 0 , N - 1 , 0 ) ; var Q = [ [ 2 , 0 , 3 ] , [ 1 , 1 , 5 ] , [ 2 , 1 , 2 ] ] ; var cntQuey = 3 ; for ( var i = 0 ; i < cntQuey ; i ++ ) { if ( Q [ i ] [ 0 ] == 1 ) { update ( tree , 0 , 0 , N - 1 , Q [ i ] [ 1 ] , Q [ i ] [ 2 ] ) ; } else { if ( Q [ i ] [ 1 ] % 2 == 0 ) { document . write ( FindSum ( tree , 0 , N - 1 , Q [ i ] [ 1 ] , Q [ i ] [ 2 ] , 0 ) + " " ) ; } else { document . write ( - FindSum ( tree , 0 , N - 1 , Q [ i ] [ 1 ] , Q [ i ] [ 2 ] , 0 ) + " " ) ; } } }