307-range-sum-query-mutable

Try it on leetcode

Description

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

1. Update the value of an element in nums.
2. 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]).

 

Example 1:

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

 

Constraints:

• 1 <= nums.length <= 3 * 104
• -100 <= nums[i] <= 100
• 0 <= index < nums.length
• -100 <= val <= 100
• 0 <= left <= right < nums.length
• At most 3 * 104 calls will be made to update and sumRange.

Solution(Python)

class NumArray:

    def __init__(self, nums: List[int]):
        self.ds = Bits(nums)

    def update(self, index: int, val: int) -> None:
        self.ds.update(index, val)

    def sumRange(self, left: int, right: int) -> int:
        return self.ds.sumRange(left, right)


        
class NaiveNumArray:
    # Time Complexity: O(n)
    def __init__(self, nums: List[int]):
        self.nums = nums

    # Time Complexity: O(1)
    def update(self, index: int, val: int) -> None:
        self.nums[index] = val 
        
    # Time Complexity: O(n)
    def sumRange(self, left: int, right: int) -> int:
        return sum(self.nums[left: right+1])
    

        
class PresumNumArray:
    # Time Complexity: O(n)
    def __init__(self, nums: List[int]):
        self.n = len(nums)
        self.nums = nums
        self.presum = [0] * (1 + self.n)
        self.build()

        
    def build(self):
        for i in range(self.n):
            self.presum[i+1] += self.presum[i] + self.nums[i]

    # Time Complexity: O(n)
    def update(self, index: int, val: int) -> None:
        diff  = val - self.nums[index]
        for i in range(index + 1, self.n):
            self.presum[i+1] +=  diff
        self.nums[index] = val
        
    # Time Complexity: O(1)
    def sumRange(self, left: int, right: int) -> int:
        if left == right:
            return self.nums[left]
        return self.presum[right + 1] -  self.presum[left]
    

    
class SegmentTree:
    # Time Complexity: O(n)
    def __init__(self, nums: List[int]):
        self.n = len(nums)
        self.tree = [0] * (2*self.n)
        self.build(nums)

        
    def build(self, nums):
        i = self.n
        j = 0
        while i< 2*self.n:
            self.tree[i] = nums[j]
            i += 1
            j += 1
        for i in range(self.n - 1, -1 ,-1):
            self.tree[i] = self.tree[i*2] + self.tree[i*2 + 1]

    # Time Complexity: O(log(n))
    def update(self, index: int, val: int) -> None:
        index += self.n
        self.tree[index] = val
        while index > 0:
            left = index
            right = index
            if index % 2 == 0:
                right = index + 1
            else:
                left = index - 1
            self.tree[index//2] = self.tree[left] + self.tree[right]
            index //= 2
    # Time Complexity: O(log(n))
    def sumRange(self, left: int, right: int) -> int:
        left += self.n
        right += self.n
        
        s = 0
        while left <= right:
            if left %2 == 1:
                s += self.tree[left]
                left += 1
            if right % 2 == 0:
                s += self.tree[right]
                right -= 1
            left //=2 
            right //=2
        return s

class Bits:
    # Time Complexity: O(nlogn)
    def __init__(self, nums: List[int]):
        self.nums = nums
        self.n = len(nums)
        self.tree = [0]*(self.n+1)
        for i in range(self.n):
            self.build(i, nums[i])
            
    def build(self, i, val):
        i += 1
        while i<=self.n:
            self.tree[i] += val
            i += i & (-i)
    # Time Complexity: O(log(n))
    def update(self, index: int, val: int) -> None:
        diff = val - self.nums[index]
        self.nums[index] = val
        self.build(index, diff)

    # Time Complexity: O(log(n))
    def sumRange(self, left: int, right: int) -> int:
        return self.sum(right) - self.sum(left-1)
    
    def sum(self, i):
        s = 0
        i += 1
        while i>0:
            s += self.tree[i]
            i -= i & (-i)
        return s


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