Queries for elements greater than K in the given index range using Segment Tree | Python3 implementation of the approach ; Merge procedure to merge two vectors into a single vector ; Final vector to return after merging ; Loop continues until it reaches the end of one of the vectors ; Here , simply add the remaining elements to the vector v ; Procedure to build the segment tree ; Reached the leaf node of the segment tree ; Recursively call the buildTree on both the nodes of the tree ; Storing the final vector after merging the two of its sorted child vector ; Query procedure to get the answer for each query l and r are query range ; out of bound or no overlap ; Complete overlap Query range completely lies in the segment tree node range ; binary search to find index of k ; Partially overlap Query range partially lies in the segment tree node range ; Function to perform the queries ; Driver code ; 1 - based indexing ; Number of queries
from bisect import bisect_left as lower_bound NEW_LINE def merge ( v1 , v2 ) : NEW_LINE INDENT i = 0 NEW_LINE j = 0 NEW_LINE v = [ ] NEW_LINE while ( i < len ( v1 ) and j < len ( v2 ) ) : NEW_LINE INDENT if ( v1 [ i ] <= v2 [ j ] ) : NEW_LINE INDENT v . append ( v1 [ i ] ) NEW_LINE i += 1 NEW_LINE DEDENT else : NEW_LINE INDENT v . append ( v2 [ j ] ) NEW_LINE j += 1 NEW_LINE DEDENT DEDENT for k in range ( i , len ( v1 ) ) : NEW_LINE INDENT v . append ( v1 [ k ] ) NEW_LINE DEDENT for k in range ( j , len ( v2 ) ) : NEW_LINE INDENT v . append ( v2 [ k ] ) NEW_LINE DEDENT return v NEW_LINE DEDENT def buildTree ( tree , arr , index , s , e ) : NEW_LINE INDENT if ( s == e ) : NEW_LINE INDENT tree [ index ] . append ( arr [ s ] ) NEW_LINE return NEW_LINE DEDENT mid = ( s + e ) // 2 NEW_LINE buildTree ( tree , arr , 2 * index , s , mid ) NEW_LINE buildTree ( tree , arr , 2 * index + 1 , mid + 1 , e ) NEW_LINE tree [ index ] = merge ( tree [ 2 * index ] , tree [ 2 * index + 1 ] ) NEW_LINE DEDENT def query ( tree , index , s , e , l , r , k ) : NEW_LINE INDENT if ( r < s or l > e ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT if ( s >= l and e <= r ) : NEW_LINE INDENT return len ( tree [ index ] ) - ( lower_bound ( tree [ index ] , k ) ) NEW_LINE DEDENT mid = ( s + e ) // 2 NEW_LINE return ( query ( tree , 2 * index , s , mid , l , r , k ) + query ( tree , 2 * index + 1 , mid + 1 , e , l , r , k ) ) NEW_LINE DEDENT def performQueries ( L , R , K , n , q , tree ) : NEW_LINE INDENT for i in range ( q ) : NEW_LINE INDENT print ( query ( tree , 1 , 0 , n - 1 , L [ i ] - 1 , R [ i ] - 1 , K [ i ] ) ) NEW_LINE DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ 7 , 3 , 9 , 13 , 5 , 4 ] NEW_LINE n = len ( arr ) NEW_LINE tree = [ [ ] for i in range ( 4 * n + 1 ) ] NEW_LINE buildTree ( tree , arr , 1 , 0 , n - 1 ) NEW_LINE L = [ 1 , 2 ] NEW_LINE R = [ 4 , 6 ] NEW_LINE K = [ 6 , 8 ] NEW_LINE q = len ( L ) NEW_LINE performQueries ( L , R , K , n , q , tree ) NEW_LINE DEDENT