Count of Ks in the Array for a given range of indices after array updates for Q queries | Javascript 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
let a ; let seg_tree ; let query ; function build_tree ( v , tl , tr ) { if ( tl != tr ) { if ( a [ tl ] == 0 ) seg_tree [ v ] = 1 ; else seg_tree [ v ] = 0 ; } else { let tm = ( tl + tr ) / 2 ; build_tree ( v * 2 , tl , tm ) ; build_tree ( v * 2 + 1 , tm + 1 , tr ) ; seg_tree [ v ] = seg_tree [ v * 2 ] + seg_tree [ v * 2 + 1 ] ; } } function frequency_zero ( v , tl , tr , l , r ) { if ( l > r ) return 0 ; if ( l == tl && r == tr ) { return seg_tree [ v ] ; } let tm = ( tl + tr ) / 2 ; return frequency_zero ( v * 2 , tl , tm , l , Math . min ( r , tm ) ) + frequency_zero ( v * 2 + 1 , tm + 1 , tr , Math . max ( l , tm + 1 ) , r ) ; } function update ( v , tl , tr , pos , new_val ) { if ( tl == tr ) { if ( new_val == 0 ) seg_tree [ v ] = 1 ; else seg_tree [ v ] = 0 ; } else { let tm = ( tl + tr ) / 2 ; if ( pos <= tm ) update ( v * 2 , tl , tm , pos , new_val ) ; else update ( v * 2 + 1 , tm + 1 , tr , pos , new_val ) ; seg_tree [ v ] = seg_tree [ v * 2 ] + seg_tree [ v * 2 + 1 ] ; } } function solve ( n , q ) { let qu = [ 5 , 3 , 6 ] ; seg_tree = new Array ( 4 * n + 1 ) ; seg_tree . fill ( 0 ) ; build_tree ( 1 , 0 , n - 1 ) ; for ( let i = 0 ; i < qu . length ; i ++ ) { document . write ( qu [ i ] + " " ) ; } for ( let i = q ; i < q ; i ++ ) { if ( query [ i - 1 ] [ 0 ] == 1 ) { let l = query [ i - 1 ] [ 1 ] ; let r = query [ i - 1 ] [ 2 ] ; document . write ( frequency_zero ( 1 , 0 , n - 1 , l , r ) + " " ) ; } else { a [ query [ i - 1 ] [ 1 ] ] = query [ i - 1 ] [ 2 ] ; let pos = query [ i - 1 ] [ 1 ] ; let new_val = query [ i - 1 ] [ 2 ] ; update ( 1 , 0 , n - 1 , pos , new_val ) ; } } } a = [ 9 , 5 , 7 , 6 , 9 , 0 , 0 , 0 , 0 , 5 , 6 , 7 , 3 , 9 , 0 , 7 , 0 , 9 , 0 ] ; let Q = 5 ; query = [ [ 1 , 5 , 14 ] , [ 2 , 6 , 1 ] , [ 1 , 0 , 8 ] , [ 2 , 13 , 0 ] , [ 1 , 6 , 18 ] ] ; let N = a . length ; solve ( N , Q ) ;