Queries to calculate sum by alternating signs of array elements in a given range | Java program to implement the above approach ; 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
import java . util . * ; class GFG { static void build ( int tree [ ] , int arr [ ] , int start , int end , int index ) { if ( start == end ) { if ( start % 2 == 0 ) { tree [ index ] = arr [ start ] ; } else { tree [ index ] = - arr [ start ] ; } return ; } int mid = start + ( 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 ] ; } static void update ( int tree [ ] , int index , int start , int end , int pos , int val ) { if ( start == end ) { if ( start % 2 == 0 ) { tree [ index ] = val ; } else { tree [ index ] = - val ; } return ; } int mid = start + ( 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 ] ; } static int FindSum ( int tree [ ] , int start , int end , int L , int R , int index ) { if ( L > end R < start ) { return 0 ; } if ( L <= start && R >= end ) { return tree [ index ] ; } int mid = start + ( end - start ) / 2 ; int X = FindSum ( tree , start , mid , L , R , 2 * index + 1 ) ; int Y = FindSum ( tree , mid + 1 , end , L , R , 2 * index + 2 ) ; return X + Y ; } public static void main ( String [ ] args ) { int arr [ ] = { 1 , 2 , 3 , 4 } ; int N = arr . length ; int tree [ ] = new int [ 4 * N + 5 ] ; Arrays . fill ( tree , 0 ) ; build ( tree , arr , 0 , N - 1 , 0 ) ; int Q [ ] [ ] = { { 2 , 0 , 3 } , { 1 , 1 , 5 } , { 2 , 1 , 2 } } ; int cntQuey = 3 ; for ( int 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 ) { System . out . print ( FindSum ( tree , 0 , N - 1 , Q [ i ] [ 1 ] , Q [ i ] [ 2 ] , 0 ) + " ▁ " ) ; } else { System . out . print ( - FindSum ( tree , 0 , N - 1 , Q [ i ] [ 1 ] , Q [ i ] [ 2 ] , 0 ) + " ▁ " ) ; } } } } }