Baekjoon 2042. 구간 합 구하기 / Python

2042. 구간 합 구하기

난이도 : 골드 1
소요 시간 : 40분
날짜 : 2025.01.01
언어 : 파이썬
알고리즘 유형 : 세그먼트 트리

설명 보기전에 문제 풀어보러 가기

1. 문제 설명

1. 숫자배열이 주어진다.
2. 커맨드들이 두 종류로 주어진다.
   • a가 1이면 b번째 숫자를 c로 바꾼다.
   • a가 2이면 b 부터 c까지의 합을 출력한다.

2. 해결 방식

1. 우선 주어진 숫자 배열에 맞게 세그먼트 트리를 만들어준다.
2. 누적 합 : 세그먼트 트리의 누적 합 구하는 알고리즘을 사용
3. 숫자 변경 : 자식 노드를 찾아 들어가면서, 변경할 인덱스가 나오면 숫자를 바꾸어 준다.
   • 이 때, 재귀함수(자식노드를 찾는)가 종료되면 그 부모 노드에서의 세그트리의 값을 갱신해주어야 한다.

3. 정답 코드

import sys; input = sys.stdin.readline

n, m, k = map(int, input().split())
graph = [int(input()) for _ in range(n)]

# 세그먼트 트리 만들어주기
seg = [0 for _ in range(4 * n)]

def make_tree(l:int=0, r:int=(n-1), x:int=1):
    if l == r:
        seg[x] = graph[l]
        return seg[x]
    mid = (l + r) // 2
    seg[x] = make_tree(l, mid, 2*x) + make_tree(mid + 1, r, 2*x + 1)
    return seg[x]

make_tree()

def find_tree(l:int, r:int, x:int, b:int, c:int):
    if c < l or r < b:return 0  # 구간 밖
    if b <= l and r <= c:return seg[x]  # 구간 < 현재 트리
    mid = (l + r) // 2
    return find_tree(l, mid, x*2, b, c) + find_tree(mid + 1, r, x*2 + 1, b, c)

# seg[idx]를 v로 바꾸기
def modify_tree(l:int, r:int, x:int, idx, v):
    if l == r == idx:
        seg[x] = v
        return
    if l > idx or r < idx:return
    mid = (l + r) // 2
    modify_tree(l, mid, x*2, idx, v)
    modify_tree(mid + 1, r, x*2 + 1, idx, v)

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

for _ in range(m + k):
    a, b, c = map(int, input().split())
    if a == 1:
        modify_tree(0, n-1, 1, b-1, c)   # 숫자 변경
    else:
        print(find_tree(0, n - 1, 1, b - 1, c - 1))  # 누적합 출력