LeetCode 솔루션 분류
[7/31] 307. Range Sum Query - Mutable
본문
Medium
3079158Add to ListShareGiven 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 indicesleft
andright
inclusive whereleft <= right
.
Implement the NumArray
class:
NumArray(int[] nums)
Initializes the object with the integer arraynums
.void update(int index, int val)
Updates the value ofnums[index]
to beval
.int sumRange(int left, int right)
Returns the sum of the elements ofnums
between indicesleft
andright
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 toupdate
andsumRange
.
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.
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)