세그먼트 트리

세그먼트 트리란?

• 배열의 범위에 대한 정보를 효율적으로 저장하고, 범위 기반 쿼리와 업데이트를 빠르게 처리할 수 있는 이진 트리 기반의 자료구조
• 불변 배열(immutable array)이나 동적인 데이터에서 빈번하게 범위 기반 쿼리를 처리할 때 유용
• 배열의 범위 정보를 트리 형태로 저장
• 리프 노드: 배열의 개별 원소
• 내부 노드: 배열의 특정 범위에 대한 연산 결과(예: 합, 최소값, 최대값 등)

세그먼트 트리에서 할 수 있는 연산

1. 범위 쿼리(Range Query):
   • 배열의 특정 구간에 대해 연산
   • 시간 복잡도: O(log N)
2. 포인트 업데이트(Point Update):
   • 배열의 특정 원소를 수정하는 연산
   • 시간 복잡도: O(log N)

세그먼트 트리 구현

구간 합 구하기

class SegmentTree:
    def __init__(self, numbers, start, end):
        self.start = start
        self.end = end
        self.mid = (end + start) // 2
        self.value = 0
        if start + 1 < end:
            self.l_child = SegmentTree(numbers, start, self.mid)
            self.r_child = SegmentTree(numbers, self.mid, end)
            self.value += self.l_child.value
            self.value += self.r_child.value
        else:
            self.value = numbers[start]
        
    def update(self, idx, value):
        if self.start + 1 == self.end:
            diff = value - self.value
            self.value = value
            return diff
        
        if self.start <= idx < self.mid:
            diff = self.l_child.update(idx, value)
            self.value += diff
            return diff 
        else:
            diff = self.r_child.update(idx, value)
            self.value += diff
            return diff 
        
    def read(self, start, end):
        if start == self.start and end == self.end:
            return self.value
        
        if end <= self.mid:
            return self.l_child.read(start, end)
        
        if self.mid <= start:
            return self.r_child.read(start, end)
        
        return self.l_child.read(start, self.mid) + self.r_child.read(self.mid, end)