Range Sum Query - Mutable

class NumArray:

    def __init__(self, nums: List[int]):
        n = len(nums)
        if n > 0:
            next_power2 = self.get_next_power2(n)
            self.tree = [0] * (next_power2 * 2 - 1)
            self.start = 0
            self.end = n - 1
            self.build_tree(self.start, self.end, 0, nums)
            self.arr = nums

    def get_next_power2(self, n):
        cnt = 0
        while n > 0:
            n >>= 1
            cnt += 1
        return 1 << cnt

    def build_tree(self, start, end, i, arr):
        if start == end:
            self.tree[i] = arr[start]
            return self.tree[i]

        mid = (start + end) // 2
        self.tree[i] = self.build_tree(start, mid, i*2+1, arr) + self.build_tree(mid+1, end, i*2+2, arr)

        return self.tree[i]

    def update(self, i: int, val: int) -> None:
        diff = val - self.arr[i]
        self.arr[i] = val
        self.update_tree(self.start, self.end, 0, i, diff)

    def update_tree(self, start, end, tree_i, arr_i, diff):

        self.tree[tree_i] += diff

        if start == end:
            return 0

        mid = (start + end) // 2

        if arr_i <= mid:
            self.update_tree(start, mid, tree_i*2+1, arr_i, diff)
        else:
            self.update_tree(mid+1, end, tree_i*2+2, arr_i, diff)

        return 0

    def sumRange(self, i: int, j: int) -> int:
        return self.get_range_sum(self.start, self.end, 0, i, j)

    def get_range_sum(self, start, end, i, range_start, range_end):

        if start >= range_start and end <= range_end:
            return self.tree[i]

        if start > range_end or end < range_start:
            return 0

        mid = (start + end) // 2

        return self.get_range_sum(start, mid, i*2+1, range_start, range_end) + self.get_range_sum(mid+1, end, i*2+2, range_start, range_end)

# Your NumArray object will be instantiated and called as such:
# obj = NumArray(nums)
# obj.update(i,val)
# param_2 = obj.sumRange(i,j)