[백준] 2042번 - 구간 합 구하기

---

문제 분석

해당 문제에서는 데이터 변경이 일어나므로, 데이터 변경시에 시간이 많이 소요되는 합 배열로는 풀 수 없다.
따라서, 세그먼트 트리의 개념을 이용해서 풀면된다.

세그 먼트 트리란

💡 구간 합, 최소 , 최대 구하는 경우에 사용될 수 있다.

다음의 3단계로 진행된다.

1. 트리 초기화
2. 질의 값 구하기
3. 데이터 업데이트 하기

트리 초기화

💡 2**k ≥ N을 만족하는 k의 최솟값을 구한 후 (2**k)*2를 트리 리스트의 크기로 정하면 된다. 예를 들어, 8개의 데이터가 존재한다고 할때, k=3 이 되며 16크기의 리스트를 만들면 된다.

이후, 만든 트리 리스트의 2^k번째 인덱스 부터 N개의 데이터를 차례대로 넣어준다.
그 다음으로는 2^(k-1) 부터 ~ 1 까지 자식노드의 인덱스 값을 통해 채운다.
(예를 들어, 구간 합의 경우 인덱스가 7인곳에는 14번째, 15번째 노드의 합을 저장한다.)

질의 값 구하기

💡 세그먼트 트리 index = 주어진 질의 index + 2^k - 1

질의 값 구하는 과정

start_index % 2 == 1일때 해당 노드 선택
end_index % 2 == 0일때 해당 노드 선택
start_index = (start_index + 1) // 2
end_index = (end_index - 1) // 2

위의 1~4 과정을 start_index ≤ end_index 까지 반복

**질의에 해당하는 노드 선택 방법

구간 합: 선택된 노드들을 모두 더한다
최댓값 구하기: 선택된 노드들 중 MAX값을 선택해 출력한다
최솟값 구하기: 선택된 노드들 중 MIN값을 선택해 출력

데이터 업데이트 하기

💡 `세그먼트 트리 index = 주어진 질의 index + 2**k - 1`

부모 노드로 이동하면서 값을 업데이트 한다.
이때 index = index // 2를 쓰면서 부모 노드로 이동한다.

---

소스 코드

import sys
input = sys.stdin.readline

N, M, K = map(int, input().split())
changeCnt = 0
start = 0

while 2**start < N:
    start += 1

arr = [0] * (2**(start + 1))
for i in range(2**start, 2**start + N):
    arr[i] = int(input())
for i in range(2**start - 1, 0, -1):
    arr[i] = arr[2*i] + arr[2*i + 1]


def getIdx(idx):
    global start
    return idx + 2**start - 1


def Change(idx, changeValue):
    changeIdx = getIdx(idx)
    arr[changeIdx] = changeValue

    while changeIdx / 2 >= 1:
        changeIdx = changeIdx // 2
        arr[changeIdx] = arr[2*changeIdx] + arr[2*changeIdx + 1]


def getSum(s, e):
    result = []
    startIdx = getIdx(s)
    endIdx = getIdx(e)

    while startIdx <= endIdx:
        if startIdx % 2 == 1:
            result.append(arr[startIdx])
        if endIdx % 2 == 0:
            result.append(arr[endIdx])
        startIdx = (startIdx + 1) // 2
        endIdx = (endIdx - 1) // 2
    return sum(result)


while changeCnt != K:
    menu, f, s = map(int, input().split())
    if menu == 1:
        Change(f, s)
    elif menu == 2:
        print(getSum(f, s))
        changeCnt += 1