# Did I implement this correctly? Segment Tree - Review please

• 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)``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.