from data_structure import SegmentTreeNode
class Solution:
    # @param start, end: Denote an segment / interval
    # @return: The root of Segment Tree
    def build(self, start, end):
        # write your code here
        node = SegmentTreeNode(start,end)
        if start > end:
            return None
        elif start != end:
            _leftStart = node.start
            _leftEnd = (node.start + node.end)/2
            node.left = self.build(_leftStart,_leftEnd)
            
            _rightStart = (node.start + node.end) / 2 + 1
            _rightEnd = node.end
            node.right = self.build(_rightStart, _rightEnd)
            
        return node
    def buildByArray(self, arr):
        def setMax(node, arr):
            interval = arr[node.start:node.end+1]
#            print interval
            node.max = max(interval)
            if node.left != None:
                setMax(node.left, arr)
            if node.right != None:
                setMax(node.right, arr)

        node = self.build(0, len(arr)-1)
        setMax(node, arr)

        return node



        


from utils import util
if __name__=='__main__':
    solution = Solution()
    segmentTree = solution.build(0,3)
    util.printSegmentTree(segmentTree)

    node = solution.buildByArray([1,4,2,3])
    util.printSegmentTree(node)