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

🔔 문제

어떤 N개의 수가 주어져 있다. 그런데 중간에 수의 변경이 빈번히 일어나고 그 중간에 어떤 부분의 합을 구하려 한다. 만약에 1,2,3,4,5 라는 수가 있고, 3번째 수를 6으로 바꾸고 2번째부터 5번째까지 합을 구하라고 한다면 17을 출력하면 되는 것이다. 그리고 그 상태에서 다섯 번째 수를 2로 바꾸고 3번째부터 5번째까지 합을 구하라고 한다면 12가 될 것이다.

입력
첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄까지 N개의 수가 주어진다. 그리고 N+2번째 줄부터 N+M+K+1번째 줄까지 세 개의 정수 a, b, c가 주어지는데, a가 1인 경우 b(1 ≤ b ≤ N)번째 수를 c로 바꾸고 a가 2인 경우에는 b(1 ≤ b ≤ N)번째 수부터 c(b ≤ c ≤ N)번째 수까지의 합을 구하여 출력하면 된다.

입력으로 주어지는 모든 수는 -263보다 크거나 같고, 263-1보다 작거나 같은 정수이다.

출력
첫째 줄부터 K줄에 걸쳐 구한 구간의 합을 출력한다. 단, 정답은 -2^63보다 크거나 같고, 2^63-1보다 작거나 같은 정수이다.

🎯 풀이방법

인덱스 트리 문제

인덱스 트리

• 포화 이진트리 형태의 자료구조
• 리프 노드 : 배열에 적혀있는 수
• 내부 노드 : 왼쪽 자식(2i)과 오른쪽 자식(2i+1)의 합

인덱스 트리 구성하기

1. 리프 노드의 수가 2^T이 되는 배열을 만든다.
2. 리프 노드에 데이터를 입력한다.
3. Bottom-Up 방식으로 리프 노드부터 루트 노드까지 양쪽 자식의 합을 구한다.
   
   

인덱스 트리의 노드 값 update

left, right : 현재 노드가 속한 범위
node : 현재 노드
target : 갱신할 leaf 노드
diff : 변경할 값(c)과 목표 노드의 원래 값의 차

1. 현재 노드(left~right)가 목표 노드에 속하지 않으면 반환
2. 현재 노드의 값을 diff만큼 갱신한다
3. 만약 현재 노드가 leaf 노드가 아니라면 왼쪽 자식과 오른쪽 자식을 update한다

구간합 구하기 (query)

left, right : 현재 노드가 속한 범위
node : 현재 노드
queryLeft, queryRight : 구하고자 하는 구간

1. 루트 노드에서 시작해서 Top-down 방식으로 탐색
2. 현재 노드(left~right)가 구하고자 하는 구간(queryLeft~queryRight)에 완전히 속해있으면 그 노드의 결과값(trees[node])를 반환
3. 아니면, 왼쪽 자식과 오른쪽 자식에서 반환된 값을 더해서 반환

💡 이 문제를 통해 얻어갈 것

인덱스 트리(Indexed Tree)를 사용하여 노드 갱신 및 구간 합 구하는 문제

💻 Python 코드

# 백준 2042번
N,M,K = map(int, input().split())

nums = []
for i in range(N):
    nums.append(int(input()))

# tree 생성
S = 1
while S < N:
    S *= 2

# 완전 이진 트리
trees = [0 for _ in range(2*S)]
for i in range(N):
    trees[S+i] = nums[i]   # leaf 노드

for i in range(S-1, 0, -1):
    trees[i] = trees[i*2] + trees[i*2+1]  # 왼쪽 자식 + 오른쪽 자식


# left, right, node : 변동
# queryLeft, queryRight : 변동 X
def query(left, right, node, queryLeft, queryRight):
    # 범위 밖 (=연관없음)
    if right < queryLeft or left > queryRight:
        return 0

    # 범위 안 (=의미 있는 값)
    elif left >= queryLeft and right <= queryRight:
        return trees[node]

    # 범위 걸쳐짐 (=판단 불가)
    mid = (left+right)//2
    leftResult = query(left, mid, node*2, queryLeft, queryRight)
    rightResult = query(mid+1, right, node*2+1, queryLeft, queryRight)
    return leftResult+rightResult


# Indexed Tree 데이터 갱신 방법
# target : 갱신할 leaf 노드 번호
def update(left, right, node, target, diff):
    # 연관 없음
    if target < left or right < target:
        return

    trees[node] += diff
    # print("updated trees[{}] = {}".format(node, trees[node]))

    # leaf 노드가 아니라면
    if left != right:
        mid = (left+right)//2

        # 왼쪽 자식 범위 update
        update(left, mid, node*2, target, diff)

        # 오른쪽 자식 범위 update
        update(mid+1, right, node*2+1, target, diff)


# update & query
for i in range(M+K):
    a, b, c = map(int, input().split())

    if a == 1:    # 수 변경
        # b번째 노드 = trees[S+b-1]
        diff = c - trees[S+b-1]

        # root 노드서부터 Top-down 방식으로 update
        update(1, S, 1, b, diff)
    else:
        result = query(1, S, 1, b, c)
        print(result)