백준 2042 구간 합 구하기 python

세그먼트 트리 3번째 문제
슬슬 익숙해 지는 것 같다.
이번 문제는 배열값의 변경과 구간 조회를 함께 요구하는 문제여서 특히 더 정석적인 문제라는 생각리 들었다.

📜 문제 바로 가기 : 구간 합 구하기

제출코드

파이썬

import sys
input = sys.stdin.readline

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

arr = [0] * N
for i in range(N):
    arr[i] = int(input())

segmentTree = [-1] * ( 4 * N )

def buildTree(node, start, end):
    if start == end:
        segmentTree[node] = arr[start]
        return arr[start]
    
    mid = (start + end) // 2
    left = buildTree(node * 2, start, mid)
    right = buildTree(node * 2 + 1, mid + 1, end)

    segmentTree[node] = left + right
    return segmentTree[node]

def upDateTree(targetIdx, value, node, start, end):
    if targetIdx < start or targetIdx > end:
        return segmentTree[node]
    
    if start == end:
        segmentTree[node] = value
        return value
    
    mid = (start + end) // 2
    left = upDateTree(targetIdx, value, node*2, start, mid)
    right = upDateTree(targetIdx, value, node*2 + 1, mid+1, end)

    segmentTree[node] = left + right
    return segmentTree[node]

def getPrefixSum(targetStart, targetEnd, node, start, end):
    if end < targetStart or targetEnd < start:
        return 0
    
    if targetStart <= start and end <= targetEnd:
        return segmentTree[node]
    
    mid = (start + end) // 2
    left = getPrefixSum(targetStart, targetEnd, node*2, start, mid)
    right = getPrefixSum(targetStart, targetEnd, node*2+1, mid+1, end)

    return left + right

buildTree(1, 0, N-1)

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

---

접근방법

별 다른 접근방법은 없고 그냥 일반적인 세그먼트 트리를 적용하면 해결된다.