307. Range Sum Query - Mutable

Range Sum Query - Mutable - LeetCode

정수로 이루어진 list가 주어질 때 주석으로 된 코드가 작동하도록 메서드를 구현하는 문제다.

class NumArray:

    def __init__(self, nums: List[int]):
        # 자유롭게 사용

    def update(self, index: int, val: int) -> None:
    	# nums[index]의 값을 val로 바꾸시오
        
    def sumRange(self, left: int, right: int) -> int:
    	# nums[left ~ right+1]의 구간합을 반환하시오
        


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

1. Brute Force -TLE

class NumArray:

    def __init__(self, nums: List[int]):
        self.nums=nums
        

    def update(self, index: int, val: int) -> None:
        self.nums[index]=val
        

    def sumRange(self, left: int, right: int) -> int:
        return sum(self.nums[left:right+1])

요구하는 바를 그대로 구현하면 위와 같은 코드가 나오고 결과는 시간 초과.

제약조건을 보면 다음과 같다.

nums의 길이가 30000이 최대다.

위에 작성한 코드를 살펴보면 update는 O(1)이다. 그냥 index에 해당하는 값을 바꿔주기 때문이다.

하지만 sumRange는 항상 O(N)이다. 특정 위치부터 위치까지의 값의 합을 구하려면 선형 탐색을 해야 하기 때문이다.

여기서 N은 3*pow(10,4)이고 sumRange가 최대 N번 호출될 수 있다고 했으니깐 3*3*pow(2, pow(10,4))...

 

시간 초과가 날 수밖에 없다.

 

2. BIT(Binary Indexed Tree, Fenwick Tree)

from typing import *


class NumArray:

    def __init__(self, nums: List[int]):
        self.nums = [0] + nums
        self.tree = [0] * (len(nums) + 1)
        for i in range(1, len(self.nums)):
            self.update_init(i, self.nums[i])

    def update_init(self, index, value):
        while index <= len(self.tree) - 1:
            self.tree[index] += value
            index += index & -index

    def update(self, index: int, val: int) -> None:
        index += 1
        gap = val - self.nums[index]
        self.update_init(index, gap)
        self.nums[index] = val

    def sumRange(self, left: int, right: int) -> int:
        left_sum = 0
        while left >= 1:
            left_sum += self.tree[left]
            left -= left & -left
        right += 1
        right_sum = 0
        while right >= 1:
            right_sum += self.tree[right]
            right -= right & -right
        return right_sum - left_sum

이 문제는 구간 질의를 해결하는 특수한 자료구조를 사용해야 한다. 구간 트리(Segment Tree)류로 불리는 자료구조를 사용하면 이 문제의 시간 복잡도를 개선할 수 있다.

구간 트리를 사용하기 전 update, sumRange의 시간 복잡도가 O(1), O(N)이었다.

구간 트리를 사용하면 각 메서드의 시간 복잡도가 O(logN), O(logN)이 된다.

 

update의 시간 복잡도가 증가했지만 결국 sunRange 메서드의 호출 횟수가 N번이 되었을 때 값의 차이는 N이 커질수록 확연하게 차이가 난다.

 

BIT 또는 Fenwick 트리라고 불리는 자료구조는 구간 트리를 간소화한 버전이다. Fenwick 트리로 해결할 수 있는 문제는 구간 트리로도 해결할 수 있지만, 그 반대는 안될 수도 있으니 참고할 것.

 

아무튼 Fenwick 트리는 sumRange의 일부 범위를 미리 prefix sum처럼 저장을 하고 값을 불러내 조합하여 원하는 결과를 구할 수 있다.