Range Sum Query - Mutable – Solution & Complexity

def range_sum_query_mutable(nums: list[int], operations: list[str], first: list[int], second: list[int]) -> list[int]:
    bit = [0] * (len(nums) + 1)

    def add(index: int, delta: int) -> None:
        index += 1
        while index < len(bit):
            bit[index] += delta
            index += index & -index

    def prefix_sum(index: int) -> int:
        total = 0
        index += 1
        while index > 0:
            total += bit[index]
            index -= index & -index
        return total

    for index, value in enumerate(nums):
        add(index, value)

    answer = []
    for operation, a, b in zip(operations, first, second):
        if operation == "update":
            delta = b - nums[a]
            nums[a] = b
            add(a, delta)
        else:
            answer.append(prefix_sum(b) - (prefix_sum(a - 1) if a > 0 else 0))

    return answer