【LeetCode】307. Area and retrieval - array modifiable

subject

307. Area and retrieval - Array can be modified

Give you an array nums , Please complete two types of queries .

1. One type of query requirements to update Array nums The value of the subscript
2. Another type of query requires the return of an array nums Middle index left And index right Between （ contain ） Of nums Elemental and , among left <= right

Realization NumArray class ：

• NumArray(int[] nums) Use an array of integers nums Initialize object
• void update(int index, int val) take nums[index] Value to update by val
• int sumRange(int left, int right) Returns an array of nums Middle index left And index right Between （ contain ） Of nums Elemental and （ namely ,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]

 explain ：
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

Tips ：

• 1 <= nums.length <= 3 * 104
• -100 <= nums[i] <= 100
• 0 <= index < nums.length
• -100 <= val <= 100
• 0 <= left <= right < nums.length
• call pdate and sumRange The number of methods shall not be greater than 3 * 104

Answer key 1(TLE)

Ideas

• Violent simulation

Code

class NumArray:

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


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

    def sumRange(self, left: int, right: int) -> int:
        return sum(self.nums[left:right+1])


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

Complexity

• initialization
  • Time complexity ：$O(1)$
  • Spatial complexity ：$O(n)$
• to update
  • Time complexity ：$O(1)$
  • Spatial complexity ：$O(1)$
• Sum up
  • Time complexity ：$O(n)$
  • Spatial complexity ：$O(1)$

Answer key 2(TLE)

Ideas

• Use an array to store prefixes and

Code

class NumArray:

    def __init__(self, nums: List[int]):
        self.nums = nums
        self.sum = []
        tempSum = nums[0]
        self.sum.append(tempSum)
        for n in nums[1:]:
            tempSum+= n
            self.sum.append(tempSum)
    def update(self, index: int, val: int) -> None:
        d = val - self.nums[index]
        self.nums[index] = val
        for i in range(index, len(self.nums)):
            self.sum[i] += d

         

    def sumRange(self, left: int, right: int) -> int:
        return self.sum[right] - self.sum[left] + self.nums[left]


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

Complexity

• initialization
  • Time complexity ：$O(n)$
  • Spatial complexity ：$O(n)$
• to update
  • Time complexity ：$O(n)$
  • Spatial complexity ：$O(1)$
• Sum up
  • Time complexity ：$O(1)$
  • Spatial complexity ：$O(1)$

Answer key 3

Ideas

• Divide the array into $\lfloor \frac{n}{\sqrt{n}}\rfloor$ paragraph , Save each paragraph and

Code

import math
class NumArray:

    def __init__(self, nums: List[int]):
        self.nums = nums
        self.size = int(len(nums)**0.5)
        self.segmentSum = [0]* math.ceil(len(nums)/self.size)
        for i,n in enumerate(nums):
            self.segmentSum[i//self.size] += n
    def update(self, index: int, val: int) -> None:
        self.segmentSum[index//self.size] += (val - self.nums[index])
        self.nums[index] = val

    def sumRange(self, left: int, right: int) -> int:
        a,b = left//self.size*self.size, (right//self.size+1)*self.size
        return sum(self.segmentSum[a//self.size:b//self.size]) - sum(self.nums[a:left]) - sum(self.nums[right+1:b])


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

Complexity

• initialization
  • Time complexity ：$O(n)$
  • Spatial complexity ：$O(\sqrt{n})$
• to update
  • Time complexity ：$O(1)$
  • Spatial complexity ：$O(1)$
• Sum up
  • Time complexity ：$O(\sqrt{n})$
  • Spatial complexity ：$O(1)$