백준 2042

<구간 합 구하기 3>

난이도 : 골드 1

1. 백준 문제
   2042

2. 코드 알고리즘

• 세그먼트 트리

• 2042

3. 코드

#2042
#https://www.acmicpc.net/problem/2042

import sys
input = sys.stdin.readline
import math

N, M, K = map(int, input().split()) #5 2 2
tree_size = math.ceil(math.log2(N)) #k = 3
tree_hight = tree_size+1
left_NodeStart = 2**(tree_size)
tree = [0]*(left_NodeStart*2) #left_NodeStart*2가 트리 리스트 크기

for i in range(left_NodeStart, left_NodeStart+N):
    tree[i] = int(input())

def toTreeIndex(index):
    while index != 0:
        tree[index//2] += tree[index]
        index -= 1

#tree 리스트 완성하기
toTreeIndex(left_NodeStart*2-1) #인덱스이므로 1만큼 빼주기
#루트노드는 무시하기

def changeNode(start_index, change):
    diff = change -tree[start_index]
    while start_index>0:
        tree[start_index] += diff #해당노드 값 변경
        start_index = start_index//2 #부모노드 값 변경

pSum = 0
def partialSum(start_index, end_index):
    global pSum
    while start_index <= end_index: #같아지는 경우까지만
        if (start_index % 2) == 1:
            pSum += tree[start_index]
            start_index += 1
        if (end_index % 2) == 0:
            pSum += tree[end_index]
            end_index -= 1
        start_index = start_index//2
        end_index = end_index//2
    return pSum

for i in range(M+K):
    a, b, c = map(int, input().split())
    if a == 1:
        start_index = b+left_NodeStart-1 #left_NodeStart = 2**k
        #데이터 순서를 세그먼트트리 리스트 인덱스로 바꿔주기
        changeNode(start_index, c)
    elif a == 2:
        pSum = 0
        start_index = b + left_NodeStart - 1
        end_index =  c + left_NodeStart - 1
        print(partialSum(start_index, end_index))

4. 코드 후기

뭣보다 세그먼트 트리 개념을 이해하는 데 시간 소요.
세그먼트 트리란 2개의 합을 트리로 나타낸 것.
(또는 최대/최소를 구할 때는 2개의 비교를 트리로 나타낸 것)

자료구조를 공부할 때는 원리를 아는 것도 중요하지만 왜 필요한 구조인지 아는 것도 중요하다 함.
세그먼트 트리는 구간합을 구할때 오래걸리는 시간이랑 데이터 업데이트가 느린 단점을 보완한것. -> 그러면 이러한 문제상황 에서 쓰이면 됨

코테 대회나가기 전 자료구조 서로 비교하고 언제 필요한 지 정리하는 것도 필요할 듯