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)