Partially overlap Query range partially lies in the segment tree node range
let mid = Math . floor ( ( s + e ) / 2 ) ; return ( query ( tree , 2 * index , s , mid , l , r , k ) + query ( tree , 2 * index + 1 , mid + 1 , e , l , r , k ) ) ; } function lowerBound ( array , length , value ) { let low = 0 ; let high = length ; while ( low < high ) { let mid = Math . floor ( ( low + high ) / 2 ) ; if ( value <= array [ mid ] ) { high = mid ; } else { low = mid + 1 ; } } return low ; }