엔지니어 게시판
LeetCode 솔루션 분류

[7/31] 307. Range Sum Query - Mutable

컨텐츠 정보

본문

Medium
3079158Add to ListShare

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.
Accepted
194,135
Submissions
495,676
태그 ,

관련자료

댓글 1

학부유학생님의 댓글

  • 익명
  • 작성일
Runtime: 5337 ms, faster than 13.07% of Python3 online submissions for Range Sum Query - Mutable.
Memory Usage: 49.4 MB, less than 10.66% of Python3 online submissions for Range Sum Query - Mutable.
class Node:
    def __init__(self, start, end):
        self.total = 0
        self.start = start
        self.end = end
        self.left = None
        self.right = None

class NumArray:

    def __init__(self, nums: List[int]):
        def createBIT(l,r):
            if l>r: return None
            # leaf
            if l == r:
                node = Node(l,r)
                node.total = nums[l]
                return node
            
            # Subtree Root
            mid = (l+r)//2
            
            root = Node(l,r)
            root.left = createBIT(l, mid)
            root.right = createBIT(mid+1, r)
            root.total = root.left.total + root.right.total
            return root
        
        self.treeroot = createBIT(0,len(nums)-1)
            

    def update(self, index: int, val: int) -> None:
        def updateVal(node, idx, val):
            # update leaf
            if node.start == node.end:
                if idx == node.start:
                    node.total = val
                return val
            
            # call recursive
            mid = (node.start +node.end)//2
            if idx <= mid:
                updateVal(node.left, idx, val)
            else:
                updateVal(node.right, idx, val)
            
            # update total
            node.total = node.left.total + node.right.total
            return node
        
        updateVal(self.treeroot, index, val)
            

    def sumRange(self, left: int, right: int) -> int:
        def rangeSum(node, l,r):
            if node.start == l and node.end == r:
                return node.total
            
            mid = (node.start+node.end)//2
            
            if r<=mid:
                return rangeSum(node.left, l, r)
            elif mid+1<=l:
                return rangeSum(node.right, l,r)
            else:
                return rangeSum(node.left, l, mid) + rangeSum(node.right, mid+1, r)
        
        return rangeSum(self.treeroot, left, right)


# Your NumArray object will be instantiated and called as such:
# obj = NumArray(nums)
# obj.update(index,val)
# param_2 = obj.sumRange(left,right)
전체 194 / 8 페이지
번호
제목
이름

최근글


인기글


새댓글


Stats


알림 0