Count of Ks in the Array for a given range of indices after array updates for Q queries | C ++ program for the above approach ; Function to build the segment tree ; Base case ; Since the count of zero is required set leaf node as 1 ; If the value in array is not zero , store 0 in the leaf node ; Find the mid ; Recursive call for left subtree ; Recursive call for right subtree ; Parent nodes contains the count of zero in range tl to tr ; Function to find the count of 0 s in range l to r ; Base Case ; Case when no two segment are combining ; Finding the mid ; When it is required to combine left subtree and right subtree to get the range l to r ; Function that updates the segment tree nodes ; Base Case ; If array element is 0 ; If array element is not 0 ; Otherwise ; Find the mid ; Update the tree or count which is stored in parent node ; Function to solve all the queries ; When query type is 1 ; When query type is 2 ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; void build_tree ( vector < int > & a , vector < int > & seg_tree , int v , int tl , int tr ) { if ( tl == tr ) { if ( a [ tl ] == 0 ) seg_tree [ v ] = 1 ; else seg_tree [ v ] = 0 ; } else { int tm = ( tl + tr ) / 2 ; build_tree ( a , seg_tree , v * 2 , tl , tm ) ; build_tree ( a , seg_tree , v * 2 + 1 , tm + 1 , tr ) ; seg_tree [ v ] = seg_tree [ v * 2 ] + seg_tree [ v * 2 + 1 ] ; } } int frequency_zero ( int v , int tl , int tr , int l , int r , vector < int > & seg_tree ) { if ( l > r ) return 0 ; if ( l == tl && r == tr ) { return seg_tree [ v ] ; } int tm = ( tl + tr ) / 2 ; return frequency_zero ( v * 2 , tl , tm , l , min ( r , tm ) , seg_tree ) + frequency_zero ( v * 2 + 1 , tm + 1 , tr , max ( l , tm + 1 ) , r , seg_tree ) ; } void update ( int v , int tl , int tr , int pos , int new_val , vector < int > & seg_tree ) { if ( tl == tr ) { if ( new_val == 0 ) seg_tree [ v ] = 1 ; else seg_tree [ v ] = 0 ; } else { int tm = ( tl + tr ) / 2 ; if ( pos <= tm ) update ( v * 2 , tl , tm , pos , new_val , seg_tree ) ; else update ( v * 2 + 1 , tm + 1 , tr , pos , new_val , seg_tree ) ; seg_tree [ v ] = seg_tree [ v * 2 ] + seg_tree [ v * 2 + 1 ] ; } } void solve ( int n , int q , vector < int > & arr , vector < vector < int > > & query ) { vector < int > seg_tree ( 4 * n + 1 , 0 ) ; build_tree ( arr , seg_tree , 1 , 0 , n - 1 ) ; for ( int i = 1 ; i <= q ; i ++ ) { if ( query [ i - 1 ] [ 0 ] == 1 ) { int l = query [ i - 1 ] [ 1 ] ; int r = query [ i - 1 ] [ 2 ] ; cout << frequency_zero ( 1 , 0 , n - 1 , l , r , seg_tree ) << ' ' ; } else { arr [ query [ i - 1 ] [ 1 ] ] = query [ i - 1 ] [ 2 ] ; int pos = query [ i - 1 ] [ 1 ] ; int new_val = query [ i - 1 ] [ 2 ] ; update ( 1 , 0 , n - 1 , pos , new_val , seg_tree ) ; } } } int main ( ) { vector < int > arr = { 9 , 5 , 7 , 6 , 9 , 0 , 0 , 0 , 0 , 5 , 6 , 7 , 3 , 9 , 0 , 7 , 0 , 9 , 0 } ; int Q = 5 ; vector < vector < int > > query = { { 1 , 5 , 14 } , { 2 , 6 , 1 } , { 1 , 0 , 8 } , { 2 , 13 , 0 } , { 1 , 6 , 18 } } ; int N = arr . size ( ) ; solve ( N , Q , arr , query ) ; return 0 ; }