307. Range Sum Query - Mutable

Given an integer array nums, handle multiple queries of the following types:

  • Update the value of an element in nums.
  • Calculate the sum of the elements of nums between indices left and right inclusive where left <= right.

Implement the NumArray class: NumArray(int[] nums) Initializes the object with the integer array nums. void update(int index, int val) Updates the value of nums[index] to be val. int sumRange(int left, int right) Returns the sum of the elements of nums between indices left and right inclusive (i.e. nums[left] + nums[left + 1] + ... + nums[right]).

Segment tree (standard implementation)

class NumArray:

    def __init__(self, nums: List[int]):
        self.N = len(nums)
        self.tree = [0] * self.N + nums
        # self.tree[0] is not used
        for i in range(self.N - 1, 0, -1):
            self.tree[i] = self.tree[2 * i] + self.tree[2 * i + 1]

    def update(self, index: int, val: int) -> None:
        pos = index + self.N
        diff = val - self.tree[pos]
        while pos > 0:
            self.tree[pos] += diff
            pos //= 2
            
    def sumRange(self, left: int, right: int) -> int:
        l = left + self.N
        r = right + self.N
        s = 0
        
        while l <= r: # When l == r, it is guaranteed that the loop will exit
            if l % 2:
                s += self.tree[l]
                l += 1
            if not r % 2:
                s += self.tree[r]
                r -= 1

            l //= 2
            r //= 2
        
        return s