307. Range Sum Query - Mutable

class SegmentTreeNode(object):
    def __init__(self, s, e):
        self.start = s # start end point 
        self.end = e # end endpoint 
        self.total = 0 # total sum within range [start, end] inclusive  
        self.left = None # left subtree 
        self.right = None # right substree
    
    @staticmethod
    def build_tree(A, s, e):
        if s > e:
            return None
        node = SegmentTreeNode(s,e)
        if s == e:
            node.total = A[s]
        else:
            mid = (s+e)//2
            node.left = SegmentTreeNode.build_tree(A,s,mid)
            node.right = SegmentTreeNode.build_tree(A,mid+1,e)
            node.total = node.left.total + node.right.total 
        return node 
    
    def update(self, i, val):
        # update at position index => need to (1)find exact leaf node to update  
        #(2) update related parent node's total 
        if self.start == self.end: #== i: # target node update  
            self.total = val
        else:
            mid = (self.start + self.end)//2
            if i <= mid:
                self.left.update(i,val)  # query range falls in left subtree
            else:
                self.right.update(i,val) # query range falls in right subtree
            self.total = self.left.total + self.right.total   # update current parent node's total

            
    def query(self,l,r):
         # termination condition:  query range match current root 
        if self.start == l and self.end == r: 
            return self.total 
        else:
            mid = (self.start + self.end)//2
            if r <= mid:
                return self.left.query(l,r)
            elif l >= mid+1:
                return self.right.query(l,r)
            else:
                # otherwise inteval is split  => need to calculate sum recursively 
                # by splitting interval 
                return self.left.query(l,mid) + self.right.query(mid+1,r)
        
class NumArray(object):
    """
    create  tree tc O(N)  sc O(N)
    update  tree tc O(lgN)     
    query : tc O(lgN)   worst case for query  tc O(N)
    
    """
    def __init__(self, nums: List[int]):
        self.root = SegmentTreeNode.build_tree(nums, 0, len(nums)-1)

    def update(self, index: int, val: int) -> None:
        self.root.update(index,val)

    def sumRange(self, left: int, right: int) -> int:
        return self.root.query(left,right)