Range Sum Query Mutable (Deprecated)

Given a mutable array of integers, find the sum of elements between i and j. Tags: Recursion, Trees

Try It!

Discussion

Video

Solution

class Node:
    def __init__(self, start, end):
        self.start = start
        self.end = end
        self.total = 0
        self.left = None
        self.right = None

class NumArray:

    def __init__(self, nums: List[int]):
        def create_tree(self, start, end):
            if start > end:
                return None
            elif start == end:
                node = Node(start, end)
                node.total = nums[start]
                return node
            else:
                mid = start + (end - start) // 2
                node = Node(start, end)
                node.left = create_tree(nums, start, mid)
                node.right = create_tree(nums, mid + 1, end)
                node.total = node.left.total + node.right.total
                return node
        
        self.root = create_tree(nums, 0, len(nums) - 1)
        

    def update(self, index: int, val: int) -> None:
        def update_val(node, index, val):
            if node.start == node.end:
                node.total = val
                return

            mid = node.start + (node.end - node.start) // 2
            if index <= mid:
                update_val(node.left, index, val)
            else:
                update_val(node.right, index, val)
            node.total = node.left.total + node.right.total
            
        update_val(self.root, index, val)

    def sumRange(self, left: int, right: int) -> int:
        def sum_range(node, i, j):
            if node.start == i and node.end == j:
                return node.total
            
            mid = node.start + (node.end - node.start) // 2
            if j <= mid:
                return sum_range(node.left, i, j)
            elif i > mid:
                return sum_range(node.right, i, j)
            else:
                return sum_range(node.left, i, mid) + sum_range(node.right, mid + 1, j)
        
        return sum_range(self.root, left, right)
        
# Your NumArray object will be instantiated and called as such:
# obj = NumArray(nums)
# obj.update(index,val)
# param_2 = obj.sumRange(left,right)