Range Queries to count the number of even parity values with updates | C ++ implementation to find number of Even Parity numbers in a subarray and performing updates ; Function that returns true if count of set bits in x is even ; parity will store the count of set bits ; A utility function to get the middle index ; Recursive function to get the number of Even Parity numbers in a given range ; If segment of this node is a part of given range , then return the number of Even Parity numbers in the segment ; If segment of this node is outside the given range ; If a part of this segment overlaps with the given range ; Recursive function to update the nodes which have the given index in their range ; Base Case : ; If the input index is in range of this node , then update the value of the node and its children ; Function to update a value in the input array and segment tree ; Check for erroneous input index ; Update the value in array ; Case 1 : Old and new values both are Even Parity numbers ; Case 2 : Old and new values both not Even Parity numbers ; Case 3 : Old value was Even Parity , new value is non Even Parity ; Case 4 : Old value was non Even Parity , new_val is Even Parity ; Update the values of nodes in segment tree ; Return number of Even Parity numbers ; Recursive function that constructs Segment Tree for the given array ; If there is one element in array , check if it is Even Parity number then store 1 in the segment tree else store 0 and return ; if arr [ segmentStart ] is Even Parity number ; If there are more than one elements , then recur for left and right subtrees and store the sum of the two values in this node ; Function to construct a segment tree from given array ; Height of segment tree ; Maximum size of segment tree ; Fill the allocated memory st ; Return the constructed segment tree ; Driver Code ; Build segment tree from given array ; Query 1 : Query ( start = 0 , end = 4 ) ; Query 2 : Update ( i = 3 , x = 11 ) , i . e Update a [ i ] to x ; Query 3 : Query ( start = 0 , end = 4 )
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define MAX  1000 NEW_LINE bool isEvenParity ( int x ) { int parity = 0 ; while ( x != 0 ) { if ( x & 1 ) parity ++ ; x = x >> 1 ; } if ( parity % 2 == 0 ) return true ; else return false ; } int getMid ( int s , int e ) { return s + ( e - s ) / 2 ; } int queryEvenParityUtil ( int * segmentTree , int segmentStart , int segmentEnd , int queryStart , int queryEnd , int index ) { if ( queryStart <= segmentStart && queryEnd >= segmentEnd ) return segmentTree [ index ] ; if ( segmentEnd < queryStart segmentStart > queryEnd ) return 0 ; int mid = getMid ( segmentStart , segmentEnd ) ; return queryEvenParityUtil ( segmentTree , segmentStart , mid , queryStart , queryEnd , 2 * index + 1 ) + queryEvenParityUtil ( segmentTree , mid + 1 , segmentEnd , queryStart , queryEnd , 2 * index + 2 ) ; } void updateValueUtil ( int * segmentTree , int segmentStart , int segmentEnd , int i , int diff , int si ) { if ( i < segmentStart i > segmentEnd ) return ; segmentTree [ si ] = segmentTree [ si ] + diff ; if ( segmentEnd != segmentStart ) { int mid = getMid ( segmentStart , segmentEnd ) ; updateValueUtil ( segmentTree , segmentStart , mid , i , diff , 2 * si + 1 ) ; updateValueUtil ( segmentTree , mid + 1 , segmentEnd , i , diff , 2 * si + 2 ) ; } } void updateValue ( int arr [ ] , int * segmentTree , int n , int i , int new_val ) { if ( i < 0 i > n - 1 ) { printf ( " Invalid ▁ Input " ) ; return ; } int diff , oldValue ; oldValue = arr [ i ] ; arr [ i ] = new_val ; if ( isEvenParity ( oldValue ) && isEvenParity ( new_val ) ) return ; if ( ! isEvenParity ( oldValue ) && ! isEvenParity ( new_val ) ) return ; if ( isEvenParity ( oldValue ) && ! isEvenParity ( new_val ) ) { diff = -1 ; } if ( ! isEvenParity ( oldValue ) && ! isEvenParity ( new_val ) ) { diff = 1 ; } updateValueUtil ( segmentTree , 0 , n - 1 , i , diff , 0 ) ; } void queryEvenParity ( int * segmentTree , int n , int queryStart , int queryEnd ) { int EvenParityInRange = queryEvenParityUtil ( segmentTree , 0 , n - 1 , queryStart , queryEnd , 0 ) ; cout << EvenParityInRange << " STRNEWLINE " ; } int constructSTUtil ( int arr [ ] , int segmentStart , int segmentEnd , int * segmentTree , int si ) { if ( segmentStart == segmentEnd ) { if ( isEvenParity ( arr [ segmentStart ] ) ) segmentTree [ si ] = 1 ; else segmentTree [ si ] = 0 ; return segmentTree [ si ] ; } int mid = getMid ( segmentStart , segmentEnd ) ; segmentTree [ si ] = constructSTUtil ( arr , segmentStart , mid , segmentTree , si * 2 + 1 ) + constructSTUtil ( arr , mid + 1 , segmentEnd , segmentTree , si * 2 + 2 ) ; return segmentTree [ si ] ; } int * constructST ( int arr [ ] , int n ) { int x = ( int ) ( ceil ( log2 ( n ) ) ) ; int max_size = 2 * ( int ) pow ( 2 , x ) - 1 ; int * segmentTree = new int [ max_size ] ; constructSTUtil ( arr , 0 , n - 1 , segmentTree , 0 ) ; return segmentTree ; } int main ( ) { int arr [ ] = { 18 , 15 , 8 , 9 , 14 , 5 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; int * segmentTree = constructST ( arr , n ) ; int start = 0 ; int end = 4 ; queryEvenParity ( segmentTree , n , start , end ) ; int i = 3 ; int x = 11 ; updateValue ( arr , segmentTree , n , i , x ) ; start = 0 ; end = 4 ; queryEvenParity ( segmentTree , n , start , end ) ; return 0 ; }