Range Sum Query - Mutable Python Solution

lcpy gen -n 307   # by problem number
lcpy gen -s range_sum_query_mutable   # by problem name

Input
["NumArray", "sumRange", "update", "sumRange"]
[[[1, 3, 5]], [0, 2], [1, 2], [0, 2]]
Output
[null, 9, null, 8]

Explanation
NumArray numArray = new NumArray([1, 3, 5]);
numArray.sumRange(0, 2); // return 1 + 3 + 5 = 9
numArray.update(1, 2);   // nums = [1, 2, 5]
numArray.sumRange(0, 2); // return 1 + 2 + 5 = 8

class NumArray:
    # Time: __init__ O(n), update O(log n), sum_range O(log n)
    # Space: O(n)
    def __init__(self, nums: list[int]) -> None:
        self.n = len(nums)
        self.nums = nums
        self.tree = [0] * (self.n + 1)
        for i, value in enumerate(nums, start=1):
            self.tree[i] += value
            parent = i + (i & -i)
            if parent <= self.n:
                self.tree[parent] += self.tree[i]

    def update(self, index: int, val: int) -> None:
        self._add(index + 1, val - self.nums[index])
        self.nums[index] = val

    def sum_range(self, left: int, right: int) -> int:
        return self._prefix(right + 1) - self._prefix(left)

    def _add(self, i: int, delta: int) -> None:
        while i <= self.n:
            self.tree[i] += delta
            i += i & -i

    def _prefix(self, i: int) -> int:
        total = 0
        while i > 0:
            total += self.tree[i]
            i -= i & -i
        return total