백준 2042번: 구간 합 구하기

백준 2042번: 구간 합 구하기

이제 막 세그먼트 트리 공부를 시작하면서 풀게 된 문제라서, 풀이는 다른 분들의 코드를 참고했다.

import sys
input = sys.stdin.readline
N,M,K = map(int,input().split())
num=[int(input()) for _ in range(N)]
seg_tree = [0 for _ in range(4*N)]

def build_tree(x,left,right):
    if left == right:
        seg_tree[x] = num[left]
        return seg_tree[x]
    mid = (left+right)//2
    left_value = build_tree(2*x, left, mid)
    right_value = build_tree(2*x+1,mid+1,right)
    seg_tree[x] = left_value+right_value
    return seg_tree[x]

build_tree(1,0,N-1)

def find_tree(b,c,x,left,right):
    if c<left or right<b:
        return 0
    if b<=left and right<=c:
        return seg_tree[x]
    mid = (left+right)//2
    left_value = find_tree(b,c,x*2,left,mid)
    right_value = find_tree(b,c,x*2+1,mid+1,right)
    return left_value+right_value

def update_tree(x,left,right,idx,val):
    if left==right==idx:
        seg_tree[x]=val
        return
    if idx<left or right<idx:
        return
    mid=(left+right)//2
    update_tree(x*2,left,mid,idx,val)
    update_tree(x*2+1,mid+1,right,idx,val)

    seg_tree[x] = seg_tree[x*2]+seg_tree[x*2+1]

for _ in range(M+K):
    a,b,c = map(int,input().split())
    if a==1:
        update_tree(1,0,N-1,b-1,c)
    else:
        s = find_tree(b-1,c-1,1,0,N-1)
        print(s)

이진 트리를 생성해서 각 트리별로 구간합을 저장하고, 그 트리를 이용해서 구간합을 구하는 문제다. 개념 자체는 어렵지 않은 것 같다. 다만 익숙해지기 전까지는 어떤 노드에 무슨 구간합을 구하는지가 좀 헷갈릴 수는 있을듯..?
그리고 구글에 검색해서 다른 글들 봤을때 세그먼트 트리가 구간합을 구하는데 일반 배열을 사용하는 것보다 유용하다는 글이 많아서 헷갈렸는데, 엄밀히 말하자면 다음과 같다.

세그먼트 트리를 생성하는 과정의 시간복잡도:O(N)
세그먼트 트리에서 구간합을 구하는 과정의 시간복잡도:O(logN)
누적합 배열을 생성하는 과정의 시간복잡도:O(N)
누적합 배열에서 구간합을 구하는 과정의 시간복잡도:O(1)

이므로 일반적으로 i~j 구간의 구간합을 구하는 문제자체는 누적합 배열이 더 유리하다고 볼 수 있다 다만 여러 개를 한꺼번에 구한다거나, 업데이트가 발생하는 경우, 최댓값 최솟값을 반복적으로 구하는 경우, 특정 조건을 만족하는 수를 구하는 경우와 같을 때 유용하다고 할 수 있다. 업데이트가 있으면 당연히 세그먼트 트리를 써야하고 그 외에는 데이터의 크기가 크고 반복적으로 값을 구할수록 세그먼트 트리가 유용한듯. 어차피 생성 과정에는 O(N)만큼 필요하니까?

세그먼트 트리에서 한 단계 더 나아간 펜윅트리의 경우, 데이터의 크기만큼만 배열을 생성해주면 되고 비트 연산을 활용한다고 한다. 세그먼트트리보다는 개념이 좀 복잡해 보여서 내일 따로 더 공부해봐야겠다.