# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def constructMaximumBinaryTree(self, nums, start=None, end=None):
        """
        :type nums: List[int]
        :rtype: TreeNode
        """
        if start is None and end is None:
            start, end = 0, len(nums)
        if start == end:
            return None
        m, mi = nums[start], start
        for i in xrange(start, end):
            if nums[i] > m:
                m, mi = nums[i], i
        ret = TreeNode(m)
        ret.left = self.constructMaximumBinaryTree(nums, start, mi)
        ret.right = self.constructMaximumBinaryTree(nums, mi + 1, end)
        return ret

@@ -200,228 +200,267 @@
 def 
-constructMaximumBinaryTree(self, nums, start=None, end=None):%0A        %22%22%22%0A        :type nums: List%5Bint%5D%0A        :rtype: TreeNode%0A        %22%22%22%0A        if start is None and end is None:%0A            start, end = 0, len(nums)
+findMax(self, start, end):%0A        bit_length = (end - start).bit_length() - 1%0A        d = 1 %3C%3C bit_length%0A        return max(self.SparseTable%5Bbit_length%5D%5Bstart%5D, self.SparseTable%5Bbit_length%5D%5Bend - d%5D)%0A%0A    def do_constructMaximumBinaryTree(self, start, end):
 %0A   
@@ -517,71 +517,196 @@
     
-m
+v
 , 
-m
 i = 
-nums%5B
+self.findMax(
 start
-%5D
 , 
-start%0A        for i in xrange(start
+end)%0A        ret = TreeNode(v)%0A        ret.left = self.do_constructMaximumBinaryTree(start, i)%0A        ret.right = self.do_constructMaximumBinaryTree(i + 1
 , end)
-:
 %0A   
@@ -714,26 +714,66 @@
     
-    if nums%5Bi%5D %3E m
+return ret%0A%0A    def constructMaximumBinaryTree(self, nums)
 :%0A  
@@ -778,24 +778,28 @@
         
+%22%22%22%0A
         
 m, mi = 
@@ -794,26 +794,29 @@
     
-m, mi = nums%5Bi%5D, i
+:type nums: List%5Bint%5D
 %0A   
@@ -812,37 +812,39 @@
 st%5Bint%5D%0A        
-ret =
+:rtype:
  TreeNode(m)%0A   
@@ -840,105 +840,341 @@
 Node
-(m)%0A        ret.left = self.constructMaximumBinaryTree(nums, start, mi)%0A        ret.right =
+%0A        %22%22%22%0A        self.SparseTable = %5B%5B(v, i) for i, v in enumerate(nums)%5D%5D%0A        l = len(nums)%0A        t = 1%0A        while t * 2 %3C l:%0A            prevTable = self.SparseTable%5B-1%5D%0A            self.SparseTable.append(%5Bmax(prevTable%5Bi%5D, prevTable%5Bi + t%5D) for i in xrange(l - t * 2 + 1)%5D)%0A            t *= 2%0A        return
  self.
+do_
 cons
@@ -1200,42 +1200,10 @@
 ree(
-nums, mi + 1, end)%0A        return ret
+0, l)
 %0A

Add py solution for 654. Maximum Binary Tree