
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


class Solution(object):
    def findMax(self, start, end):
        bit_length = (end - start).bit_length() - 1
        d = 1 << bit_length
        return max(self.SparseTable[bit_length][start], self.SparseTable[bit_length][end - d])

    def do_constructMaximumBinaryTree(self, start, end):
        if start == end:
            return None
        v, i = self.findMax(start, end)
        ret = TreeNode(v)
        ret.left = self.do_constructMaximumBinaryTree(start, i)
        ret.right = self.do_constructMaximumBinaryTree(i + 1, end)
        return ret

    def constructMaximumBinaryTree(self, nums):
        """
        :type nums: List[int]
        :rtype: TreeNode
        """
        self.SparseTable = [[(v, i) for i, v in enumerate(nums)]]
        l = len(nums)
        t = 1
        while t * 2 < l:
            prevTable = self.SparseTable[-1]
            self.SparseTable.append([max(prevTable[i], prevTable[i + t]) for i in xrange(l - t * 2 + 1)])
            t *= 2
        return self.do_constructMaximumBinaryTree(0, l)

Add py solution for 654. Maximum Binary Tree
Add py solution for 654. Maximum Binary Tree

654. Maximum Binary Tree: https://leetcode.com/problems/maximum-binary-tree/

    Approach 2:
    1. Use [Sparse Table](https://wcipeg.com/wiki/Range_minimum_query#Sparse_table)
    to quickly lookup maximum and its index
    2. However, approach 1 is already O(nlogn) (average case), approach 2
    is much slower compared to approach 1

  
  class Solution(object):
+     def findMax(self, start, end):
+         bit_length = (end - start).bit_length() - 1
+         d = 1 << bit_length
+         return max(self.SparseTable[bit_length][start], self.SparseTable[bit_length][end - d])
+ 
-     def constructMaximumBinaryTree(self, nums, start=None, end=None):
+     def do_constructMaximumBinaryTree(self, start, end):
+         if start == end:
+             return None
+         v, i = self.findMax(start, end)
+         ret = TreeNode(v)
+         ret.left = self.do_constructMaximumBinaryTree(start, i)
+         ret.right = self.do_constructMaximumBinaryTree(i + 1, end)
+         return ret
+ 
+     def constructMaximumBinaryTree(self, nums):
          """
          :type nums: List[int]
          :rtype: TreeNode
          """
+         self.SparseTable = [[(v, i) for i, v in enumerate(nums)]]
+         l = len(nums)
+         t = 1
+         while t * 2 < l:
+             prevTable = self.SparseTable[-1]
+             self.SparseTable.append([max(prevTable[i], prevTable[i + t]) for i in xrange(l - t * 2 + 1)])
+             t *= 2
-         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)
+         return self.do_constructMaximumBinaryTree(0, l)
-         ret.right = self.constructMaximumBinaryTree(nums, mi + 1, end)
-         return ret
  
Add py solution for 654. Maximum Binary Tree
## Code Before:

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

## Instruction:
Add py solution for 654. Maximum Binary Tree
## Code After:

class Solution(object):
    def findMax(self, start, end):
        bit_length = (end - start).bit_length() - 1
        d = 1 << bit_length
        return max(self.SparseTable[bit_length][start], self.SparseTable[bit_length][end - d])

    def do_constructMaximumBinaryTree(self, start, end):
        if start == end:
            return None
        v, i = self.findMax(start, end)
        ret = TreeNode(v)
        ret.left = self.do_constructMaximumBinaryTree(start, i)
        ret.right = self.do_constructMaximumBinaryTree(i + 1, end)
        return ret

    def constructMaximumBinaryTree(self, nums):
        """
        :type nums: List[int]
        :rtype: TreeNode
        """
        self.SparseTable = [[(v, i) for i, v in enumerate(nums)]]
        l = len(nums)
        t = 1
        while t * 2 < l:
            prevTable = self.SparseTable[-1]
            self.SparseTable.append([max(prevTable[i], prevTable[i + t]) for i in xrange(l - t * 2 + 1)])
            t *= 2
        return self.do_constructMaximumBinaryTree(0, l)
