Queries to count array elements greater than or equal to a given number with updates | Function to build a segment tree ; Check for base case ; Find mid point ; Recursively build the segment tree ; Function for push down operation on the segment tree ; Function to update the segment tree ; Complete overlap ; Find mid ; Perform push down operation on segment tree ; Recursively update the segment tree ; Function to process the query ; Base case ; Find mid ; Perform push down operation on segment tree ; Recursively calculate the result of the query ; Return the result ; Function to count the numbers which are greater than the given query ; Sort the input array ; Create segment tree of size 4 * n ; Build the segment tree ; Iterate over the queries ; Store result in array ; Update the elements in the given range ; Print the result of queries ; Driver Code ; Function call
function build ( sum , a , l , r , rt ) { if ( l == r ) { sum [ rt ] = a [ l - 1 ] ; return ; } let m = ( l + r ) >> 1 ; build ( sum , a , l , m , rt << 1 ) ; build ( sum , a , m + 1 , r , rt << 1 1 ) ; } function pushDown ( sum , add , rt , ln , rn ) { if ( add [ rt ] != 0 ) { add [ rt << 1 ] = add [ rt ] ; add [ rt << 1 1 ] = add [ rt ] ; sum [ rt << 1 ] = sum [ rt << 1 ] + add [ rt ] * ln ; sum [ rt << 1 1 ] = sum [ rt << 1 1 ] + add [ rt ] * rn ; add [ rt ] = 0 ; } } function update ( sum , add , L , R , C , l , r , rt ) { if ( L <= l && r <= R ) { sum [ rt ] = sum [ rt ] + C * ( r - l + 1 ) ; add [ rt ] = add [ rt ] + C ; return ; } let m = ( l + r ) >> 1 ; pushDown ( sum , add , rt , m - l + 1 , r - m ) ; if ( L <= m ) { update ( sum , add , L , R , C , l , m , rt << 1 ) ; } if ( R > m ) { update ( sum , add , L , R , C , m + 1 , r , rt << 1 1 ) ; } } function query ( sum , add , L , R , l , r , rt ) { if ( L <= l && r <= R ) { return sum [ rt ] ; } let m = ( l + r ) >> 1 ; pushDown ( sum , add , rt , m - l + 1 , r - m ) ; let ans = 0 ; if ( L <= m ) { ans += query ( sum , add , L , R , l , m , rt << 1 ) ; } if ( R > m ) { ans += query ( sum , add , L , R , m + 1 , r , rt << 1 1 ) ; } return ans ; } function sequenceMaintenance ( n , q , a , b , m ) { a . sort ( function ( a , b ) { return a - b ; } ) ; let sum = [ ] ; let ad = [ ] ; let ans = [ ] ; for ( let i = 0 ; i < ( n << 2 ) ; i ++ ) { sum . push ( 0 ) ; ad . push ( 0 ) ; } build ( sum , a , 1 , n , 1 ) ; for ( let i = 0 ; i < q ; i ++ ) { let l = 1 , r = n , pos = - 1 ; while ( l <= r ) { m = ( l + r ) >> 1 ; if ( query ( sum , ad , m , m , 1 , n , 1 ) >= b [ i ] ) { r = m - 1 ; pos = m ; } else { l = m + 1 ; } } if ( pos == - 1 ) { ans . push ( 0 ) ; } else { ans . push ( n - pos + 1 ) ; update ( sum , ad , pos , n , - m , 1 , n , 1 ) ; } } for ( let i = 0 ; i < ans . length ; i ++ ) { document . write ( ans [ i ] + " " ) ; } } let N = 4 ; let Q = 3 ; let M = 1 ; let arr = [ 1 , 2 , 3 , 4 ] ; let Query = [ 4 , 3 , 1 ] ; sequenceMaintenance ( N , Q , arr , Query , M ) ;