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

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

• 학부유학생 작성
• 작성일

• 120 조회
• 1 댓글

### 본문

Medium

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)``````
전체 175 / 1 페이지

• 등록일 21:33
• 등록일 20:51
• 등록일 19:57
• 등록일 18:58
• 등록일 18:48
• 등록일 17:52
• 등록일 17:49
• 등록일 17:47
• 등록일 16:26
• 등록일 16:24
• 등록일 16:21
• 등록일 16:18
• 등록일 16:16
• 등록일 16:14
• 등록일 16:10
• 등록일 16:07

### 새댓글

• 등록자 학부유학생 등록일 21:34
• 등록자 학부유학생 등록일 08.08
• 등록자 학부유학생 등록일 08.08
• 등록자 학부유학생 등록일 08.07
• 등록자 학부유학생 등록일 08.05
• 등록자 진호 등록일 08.05
• 등록자 JKP 등록일 08.05
• 등록자 Joy 등록일 08.04
• 등록자 학부유학생 등록일 08.02
• 등록자 mingki 등록일 08.02
• 등록자 학부유학생 등록일 08.01
• 등록자 mingki 등록일 07.31
• 등록자 학부유학생 등록일 07.31
• 등록자 학부유학생 등록일 07.31
• 등록자 학부유학생 등록일 07.30
• 등록자 Eujin 등록일 07.29