Problem statement

https://leetcode.com/problems/range-sum-query-mutable/

Solution

There are two classical way how you can solve this problem: segment trees or binary indexed trees. The second one is easier to code. For more definition of BIT, see wikipedia: https://en.wikipedia.org/wiki/Fenwick_tree

Here we need not to update value by delta as it is done in classical implementation, but replace number. So we need to keep both BIT and original array: we keep self.bit: our tree and self.nums our nums. When we do initialization, here I do it not in optimal way: we update number by number in our BIT: so total complexity of initialization will be O(n log n) - there exists also O(n) way to do it, but it is more difficult to code. Inside function update we update both BIT and self.nums. Finally, to evaluate sumRange, we apply two times query: query(x) returns sum of first x elements.

Complexity

Space complexity is O(n) for whole data structure. Time complexity of initialization is O(n log n), time complexity of update and sumRange is O(log n).

Code

class BIT:
    def __init__(self, n):
        self.sums = [0] * (n+1)
    
    def update(self, i, delta):
        while i < len(self.sums):
            self.sums[i] += delta
            i += i & (-i)
    
    def query(self, i):
        res = 0
        while i > 0:
            res += self.sums[i]
            i -= i & (-i)
        return res

class NumArray:
    def __init__(self, nums):
        self.bit = BIT(len(nums))
        for i, num in enumerate(nums):
            self.bit.update(i+1, num)
        self.nums = [0] + nums

    def update(self, i, val):
        self.bit.update(i+1, val - self.nums[i+1])
        self.nums[i+1] = val

    def sumRange(self, i, j):
        return self.bit.query(j+1) - self.bit.query(i)