LeetCode 솔루션

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

학부유학생 쪽지보내기 메일보내기 자기소개 아이디로 검색 전체게시물 작성
작성일 2022.07.31 10:49

16,083 조회
1 댓글
0 추천
0 비추천
목록

글검색

게시글 쓰기

307. Range Sum Query - Mutable

Medium

3079158Add to ListShare

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

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

#Google, #Amazon

링크

https://leetcode.com/problems/range-sum-query-mutable/ 3458 회 연결

익명
작성일 2022.07.31 10:49

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)

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.
[code=Python 3]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)[/code]