Range Update Queries to XOR with 1 in a Binary Array . | C ++ program for the given problem ; Class for each node in the segment tree ; A utility function for merging two nodes ; utility function for updating a node ; A recursive function that constructs Segment Tree for given string ; If start is equal to end then insert the array element ; Build the segment tree for range qs to mid ; Build the segment tree for range mid + 1 to qe ; merge the two child nodes to obtain the parent node ; Query in a range qs to qe ; If the range lies in this segment ; If the range is out of the bounds of this segment ; Else query for the right and left child node of this subtree and merge them ; range update using lazy prpagation ; If the range is out of the bounds of this segment ; If the range lies in this segment ; Else query for the right and left child node of this subtree and merge them ; Driver code ; Build the segment tree ; Query of Type 2 in the range 3 to 7 ; Query of Type 3 in the range 2 to 5 ; Query of Type 1 in the range 1 to 4 ; Query of Type 4 in the range 3 to 7 ; Query of Type 5 in the range 4 to 9
#include <bits/stdc++.h> NEW_LINE using namespace std ; int lazy [ 100001 ] ; class node { public : int l1 , r1 , l0 , r0 ; int min0 , max0 , min1 , max1 ; node ( ) { l1 = r1 = l0 = r0 = -1 ; max1 = max0 = INT_MIN ; min1 = min0 = INT_MAX ; } } seg [ 100001 ] ; node MergeUtil ( node l , node r ) { node x ; x . l0 = ( l . l0 != -1 ) ? l . l0 : r . l0 ; x . r0 = ( r . r0 != -1 ) ? r . r0 : l . r0 ; x . l1 = ( l . l1 != -1 ) ? l . l1 : r . l1 ; x . r1 = ( r . r1 != -1 ) ? r . r1 : l . r1 ; x . min0 = min ( l . min0 , r . min0 ) ; if ( l . r0 != -1 && r . l0 != -1 ) x . min0 = min ( x . min0 , r . l0 - l . r0 ) ; x . min1 = min ( l . min1 , r . min1 ) ; if ( l . r1 != -1 && r . l1 != -1 ) x . min1 = min ( x . min1 , r . l1 - l . r1 ) ; x . max0 = max ( l . max0 , r . max0 ) ; if ( l . l0 != -1 && r . r0 != -1 ) x . max0 = max ( x . max0 , r . r0 - l . l0 ) ; x . max1 = max ( l . max1 , r . max1 ) ; if ( l . l1 != -1 && r . r1 != -1 ) x . max1 = max ( x . max1 , r . r1 - l . l1 ) ; return x ; } node UpdateUtil ( node x ) { swap ( x . l0 , x . l1 ) ; swap ( x . r0 , x . r1 ) ; swap ( x . min1 , x . min0 ) ; swap ( x . max0 , x . max1 ) ; return x ; } void Build ( int qs , int qe , int ind , int arr [ ] ) { if ( qs == qe ) { if ( arr [ qs ] == 1 ) { seg [ ind ] . l1 = seg [ ind ] . r1 = qs ; } else { seg [ ind ] . l0 = seg [ ind ] . r0 = qs ; } lazy [ ind ] = 0 ; return ; } int mid = ( qs + qe ) >> 1 ; Build ( qs , mid , ind << 1 , arr ) ; Build ( mid + 1 , qe , ind << 1 1 , arr ) ; seg [ ind ] = MergeUtil ( seg [ ind << 1 ] , seg [ ind << 1 1 ] ) ; } node Query ( int qs , int qe , int ns , int ne , int ind ) { if ( lazy [ ind ] != 0 ) { seg [ ind ] = UpdateUtil ( seg [ ind ] ) ; if ( ns != ne ) { lazy [ ind * 2 ] ^= lazy [ ind ] ; lazy [ ind * 2 + 1 ] ^= lazy [ ind ] ; } lazy [ ind ] = 0 ; } node x ; if ( qs <= ns && qe >= ne ) return seg [ ind ] ; if ( ne < qs ns > qe ns > ne ) return x ; int mid = ( ns + ne ) >> 1 ; node l = Query ( qs , qe , ns , mid , ind << 1 ) ; node r = Query ( qs , qe , mid + 1 , ne , ind << 1 1 ) ; x = MergeUtil ( l , r ) ; return x ; } void RangeUpdate ( int us , int ue , int ns , int ne , int ind ) { if ( lazy [ ind ] != 0 ) { seg [ ind ] = UpdateUtil ( seg [ ind ] ) ; if ( ns != ne ) { lazy [ ind * 2 ] ^= lazy [ ind ] ; lazy [ ind * 2 + 1 ] ^= lazy [ ind ] ; } lazy [ ind ] = 0 ; } if ( ns > ne ns > ue ne < us ) return ; if ( ns >= us && ne <= ue ) { seg [ ind ] = UpdateUtil ( seg [ ind ] ) ; if ( ns != ne ) { lazy [ ind * 2 ] ^= 1 ; lazy [ ind * 2 + 1 ] ^= 1 ; } return ; } int mid = ( ns + ne ) >> 1 ; RangeUpdate ( us , ue , ns , mid , ind << 1 ) ; RangeUpdate ( us , ue , mid + 1 , ne , ind << 1 1 ) ; node l = seg [ ind << 1 ] , r = seg [ ind << 1 1 ] ; seg [ ind ] = MergeUtil ( l , r ) ; } int main ( ) { int arr [ ] = { 1 , 1 , 0 , 1 , 0 , 1 , 0 , 1 , 0 , 1 , 0 , 1 , 1 , 0 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; Build ( 0 , n - 1 , 1 , arr ) ; node ans = Query ( 3 , 7 , 0 , n - 1 , 1 ) ; cout << ans . min1 << " STRNEWLINE " ; ans = Query ( 2 , 5 , 0 , n - 1 , 1 ) ; cout << ans . max1 << " STRNEWLINE " ; RangeUpdate ( 1 , 4 , 0 , n - 1 , 1 ) ; ans = Query ( 3 , 7 , 0 , n - 1 , 1 ) ; cout << ans . min0 << " STRNEWLINE " ; ans = Query ( 4 , 9 , 0 , n - 1 , 1 ) ; cout << ans . max0 << " STRNEWLINE " ; return 0 ; }