Range Sum Query - Mutable

Description

Given an integer array nums, and then you need to implement two functions:

• update(i, val) Modify the element whose index is i to val.

• sumRange(l, r) Return the sum of elements whose indexes are in range of $[l, r][l,r]$.

1. The array is only modifiable by the update function.

2. You may assume the number of calls to update and sumRange function is distributed evenly.

Example

Example 1:

Input: 
  nums = [1, 3, 5]
  sumRange(0, 2)
  update(1, 2)
  sumRange(0, 2)
Output:
  9
  8

Example 2:

Input:
  nums = [0, 9, 5, 7, 3]
  sumRange(4, 4)
  sumRange(2, 4)
  update(4, 5)
  update(1, 7)
  update(0, 8)
  sumRange(1, 2)
Output:
  3
  15
  12

class NumArray(object):
    class SegmentTree:
        def __init__(self, start,end , val):
            self.start, self.end , self.val = start,end , val 
            self.left, self.right = None, None
    
    def Build(self, nums, start, end ):
        root = self.SegmentTree(start, end , nums[start])
        if start >= end:
            return root 
        mid = (start + end ) / 2 
        root.left = self.Build(nums, start, mid )
        root.right = self.Build(nums, mid + 1, end )
        if root.left and root.right:
            root.val = root.left.val + root.right.val
        return root 
       

    def __init__(self, nums):
        """
        :type nums: List[int]
        """
        if len(nums) == 0:
            return None
        self.root = self.Build(nums, 0, len(nums) - 1 )
        

    def modify(self,root,index, val):
        if root.start == root.end:
            root.val = val
            return
        if root is None:
            return None
        if root.left.end < index:
            self.modify(root.right,index,val)
        else:
            self.modify(root.left, index,val)
        root.val = root.left.val + root.right.val
            
    
    def update(self, i, val):
        """
        :type i: int
        :type val: int
        :rtype: void
        """
        return self.modify(self.root, i, val )
    
        

    def sumRange(self, i, j):
        """
        :type i: int
        :type j: int
        :rtype: int
        """
        return self.query(i,j,self.root)
        
        
    def query(self, start,end , root):
        if start > end:
            return 0
        if root.start >= start and root.end <= end:
            return root.val
        if start > root.end or end < root.start:
            return 0
        return self.query(start,end,root.left) + self.query(start,end, root.right)