백준 2268 : 수들의 합 7 (Python)

본문 링크

import sys
input=sys.stdin.readline

def Modify(node, start , end , index , value) :

    if index<start or index>end:
        return

    if start==end:
        tree[node]=value
        return

    Modify(node*2 , start , (start+end)//2 , index , value)
    Modify(node*2+1 , (start+end)//2+1 , end , index , value)

    tree[node]=tree[node*2]+tree[node*2+1]


def Sum(node , start , end , left , right):


    if left>end or right<start:
        return 0

    if left<=start and right>=end:
        return tree[node]

    return Sum(node*2 , start , (start+end)//2 , left , right) + Sum(node*2+1 , (start+end)//2+1 , end , left , right)

N,M=map(int,input().split())
tree=[0]*(4*N)
L=[0]*N
for i in range(M):

    Q,A,B=map(int,input().split())


    if Q==0:
        if A > B:
            A, B = B, A
        print( Sum(1 , 0 , N-1, A-1 , B-1) )
    else:
        Modify(1,0,N-1 , A-1, B)

📌 어떻게 접근할 것인가?

세그먼트 트리를 사용해서 풀었습니다.
초기값은 전부다 $0$ 이므로 굳이 init 함수를 따로 만들어서 초기화 할 필요는 없습니다.

값을 변경하는 함수와 합을 구하는 함수를 만들어 주었습니다.

이때 주의해야할 점은 Sum 을 구할때 A,B 의 값이 꼭 오름차순이 아닐 수 있기 때문에 정렬해주었습니다.

값을 변경할때는 A 번쨰 인덱스값을 B 로만 바꾸는 것이기 때문에 함수를 한번만 실행하였고
인덱스로 사용할때는 -1 을 해주었습니다.