307. Range Sum Query - Mutable

슬 난이도 좀 올려봅시다 !

https://leetcode.com/problems/range-sum-query-mutable/

Range Sum Query - Mutable - LeetCode

본 문제는 구간합 문제입니다. 구간합이라함은 i ~ j 까지 데이터의 합을 말합니다.

 

이 문제에서는 update라는 메소드가 존재를 하는데 본 메소드를 통해서 값을 변경해나갑니다. 그 변경 값에 대한 구간합도 당연히 초기화가 되겠죠.

 

이를 염두할 수 있는 자료구조가 바로 Segment Tree 입니다 !!

---

Segment Tree란?

이보다 완벽한 그림이 또 있을까?

Segment Tree란 N개의 데이터들의 구간합을 명시하는 트리입니다.

 

사실 구간합이 아니어도 됩니다.

 

구간곱, 구간 빼기 등등 여러분들 입 맛대로 두 데이터를 종합하여 표현만 할 수 있다면 어떤 것이든 가능합니다. (보통 구간합으로 설명을 많이하죠.

 

N개의 데이터가 있다고 합시다. 그렇다면 최정상의 노드는 1 ~ N개의 구간에 대한 정보를 전부 다 담고 있겠죠? (위 그림에는 0번 인덱스라고 하지만 Tree 특성상 1번 인덱스부터 나가는게 편하니 1이라고 했습니다)

 

거기서 왼쪽, 오른쪽 노드로 가지를 펼칠건데, 이 왼쪽, 오른쪽을 나누는 기준이 바로 중간값(mid)입니다.

 

이 미드는 해당 노드의 시작값과 끝값을 더해서 2로 나눈 값입니다. (mid = (s + e) / 2) 최정상 노드에서 s는 1, e 는 N이 되겠죠. (N개의 데이터니까 말이죠)

 

그 미드값을 중심으로 왼쪽, 오른쪽 가지를 펼치다보면 어느순간 !? s와 e가 같게되는 순간이 올 것입니다. 그 자리가 데이터가 들어가는 곳이죠.

 

제가 N개의 데이터들이라고 말을 했었죠? 그 N 개의 데이터들은 전부 마지막 노드(자식 노드가 없는 노드)를 담당하게 됩니다.

 

거기에 저희가 원하는 데이터를 넣으면 됩니다. 그러면 Segment Tree 완성 !

---

본 문제를 풀기위한 Segment Tree를 짰는데, 코드를 보도록 합시다.

 

class NumArray:

    def __init__(self, nums: List[int]):
        self.tree = [0 for i in range(len(nums) * 3)]
        self.nums = nums
        
        for key, value in enumerate(nums):
            self.seg_update(1, 1, len(nums), key + 1, value)
        
        
    def seg_update(self, node: int, s: int, e: int, idx: int, data: int):
        if s == e:
            self.tree[node] = data
            return 0
        
        mid = (s + e) // 2
        
        if idx <= mid:
            self.seg_update(node * 2, s, mid, idx, data)
        else:
            self.seg_update(node * 2 + 1, mid + 1, e, idx, data)
        
        self.tree[node] = self.tree[node * 2] + self.tree[node * 2 + 1]
        
    
    def query(self, node: int, s: int, e: int, qs: int, qe: int):
        if (qe < s or e < qs):
            return 0
        elif (qs <= s and e <= qe):
            return self.tree[node]
        else:
            mid = (s + e) // 2
            return self.query(node * 2, s, mid, qs, qe) + self.query(node * 2 + 1, mid + 1, e, qs, qe)
    
    def update(self, i: int, val: int) -> None:
        self.seg_update(1, 1, len(self.nums), i + 1, val)

    
    def sumRange(self, i: int, j: int) -> int:
        return self.query(1, 1, len(self.nums), i + 1, j + 1)


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

저희가 주목해야하는 2가지 메소드는 seg_update와 query 메소드입니다.

 

seg_update는 앞서 말했듯이 원하는 위치에 데이터를 집어넣는 역할을 하게 되는데, 보통 주어진 데이터를 순차적으로 넣기 때문에, idx와 data를 같이 넘겼습니다. 당연히 s, e의 초기값은 1, N이겠죠.

 

인자 node는 무엇일까요? 인자 node는 최정상 노드에서 탐색을 담당하는 인자로서 1의 값을 초기값으로 합니다. 즉, 트리 내에서 적재적소에 넣을 공간을 찾았다는 말은 tree라는 배열안에 넣을 idx를 찾았다는 말과 똑같은데, 그 tree[idx]에서 idx를 담당하는 인자가 바로 node입니다.

 

그렇다면 seg_update로 데이터를 넣었다고 친다면, 이를 확인할 때 사용하는 함수도 있어야겠죠? 그 담당을 query라는 친구가 합니다.

 

역시, node라는 인자를 받고, 초기값을 1과 N으로 받는 s와 e도 있습니다. qs와 qe가 원하는 범위를 나타내는 인자(인덱스)입니다.

 

메소드 내의 s와 e가 qs, qe를 벗어난다면 굳이 탐색을 할 필요가 없으니 0을 리턴하고, 안에 쏙 들어오면 그 순간의 tree[node]를 리턴해줍니다. 그 노드의 자식들의 값이 본인인데 더 자식을 타고 들어갈 필요가 없으니까요.

 

현재 메소드의 s와 e가 걸친다면 어떻게 될까요? 더 쪼개서 재귀를 돌리면 됩니다. 그 순간이 올 때까지

 

이렇게 Segment Tree를 사용하여 해결할 수 있는 문제였습니다.

---

이상 307. Range Sum Query - Mutable 였습니다. ^_^