I was asked to find minimum or maximum from a given range in an array of millions of unsorted elements. Elements wont change but query should be efficient. Now I thought of "segment tree" conceptually and implemented this. Is this really a good implementation or answers the question correctly? Of course I couldn't write code like below but conveyed the idea...does this look okay?
class Node(object): def __init__(self,start,end,left=None,right=None): self.start = start self.end = end self.left = left self.right = right class SegmentTree(object): def __init__(self,nums): self.root = None self.nums = nums # append all elements of array and their range in queue q =  for i in range(len(nums)): node = Node(i,i) q.append(node) n = len(nums) # if n or number of items is not power of 2 if ( n & (n-1)) != 0: # count nearest power of two greater than n i = 1 while i < n: i <<= 1 # add dumy nodes to have full binary tree for x in range((i-n)): self.nums.append(-sys.maxsize) q.append(Node(n+x,n+x)) # must have at least 2 items in queue to form a parent while len(q) > 1: # pop first two! left = q.pop(0) right = q.pop(0) # make a root! merge their ranges! root = Node(left.start, right.end, left, right) q.append(root) # when only one item in queue, its root! self.root = q.pop() def __findMaxAtRoot(self,root,start,end): if root: # if either end of range represents a node of tree, return its value if root.start == start and root.end == start or root.start == end and root.end == end: return self.nums[root.start] if root.start <= start <= root.end or root.start <= end <= root.end: # start falls with in a range or end falls with in a range of a node # send query to its children maxl = self.__findMaxAtRoot(root.left,start,end) maxr = self.__findMaxAtRoot(root.right,start,end) return max(maxl,maxr) # if range falls outside control of node, return -sys.maxsize return -sys.maxsize def findMax(self,start,end): return self.__findMaxAtRoot(self.root,start,end)