Queries for elements greater than K in the given index range using Segment Tree | Python implementation of the approach ; combine function to make parent node ; building the tree ; leaf node ; merging the nodes while backtracking ; performing query ; out of bounds ; complete overlaps ; partial overlaps ; Driver Code ; 1 - based indexing
import math NEW_LINE def combine ( a , b ) : NEW_LINE INDENT if a != 0 and b != 0 : NEW_LINE INDENT return a NEW_LINE DEDENT if a >= b : NEW_LINE INDENT return a NEW_LINE DEDENT return b NEW_LINE DEDENT def build_tree ( arr , tree , ind , low , high , x ) : NEW_LINE INDENT if low == high : NEW_LINE INDENT if arr [ low ] > x : NEW_LINE INDENT tree [ ind ] = arr [ low ] NEW_LINE DEDENT else : NEW_LINE INDENT tree [ ind ] = 0 NEW_LINE DEDENT return NEW_LINE DEDENT mid = ( high - low ) / 2 + low NEW_LINE mid = math . floor ( mid ) NEW_LINE mid = int ( mid ) NEW_LINE build_tree ( arr , tree , 2 * ind + 1 , low , mid , x ) NEW_LINE build_tree ( arr , tree , 2 * ind + 2 , mid + 1 , high , x ) NEW_LINE tree [ ind ] = combine ( tree [ 2 * ind + 1 ] , tree [ 2 * ind + 2 ] ) NEW_LINE DEDENT def query ( tree , ind , low , high , l , r ) : NEW_LINE INDENT mid = ( high - low ) / 2 + low NEW_LINE mid = math . floor ( mid ) NEW_LINE mid = int ( mid ) NEW_LINE if low > r or high < l : NEW_LINE INDENT return 0 NEW_LINE DEDENT if l <= low and r >= high : NEW_LINE INDENT return tree [ ind ] NEW_LINE DEDENT q1 = query ( tree , 2 * ind + 1 , low , mid , l , r ) NEW_LINE q2 = query ( tree , 2 * ind + 2 , mid + 1 , high , l , r ) NEW_LINE return combine ( q1 , q2 ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ 7 , 3 , 9 , 13 , 5 , 4 ] NEW_LINE n = len ( arr ) NEW_LINE k = 6 NEW_LINE tree = [ [ ] for i in range ( 4 * n ) ] NEW_LINE l = 1 NEW_LINE r = 4 NEW_LINE build_tree ( arr , tree , 0 , 0 , n - 1 , k ) NEW_LINE print ( query ( tree , 0 , 0 , n - 1 , l - 1 , r - 1 ) ) NEW_LINE DEDENT