백준 12837 : 가계부 (Hard) (Python)

본문 링크

import sys
input=sys.stdin.readline

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

    if index<start or index>end:
        return

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

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

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

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

    if left>end or right<start:
        return 0

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

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



N,Q=map(int,input().split())

tree=[0]*(4*N)
for i in range(Q):

    q,a,b=map(int,input().split())

    if q==1:
        update(1,0,N-1,a-1, b)
    else:
        print( query(1 , 0 , N-1 , a-1 , b-1))

📌 어떻게 접근할 것인가?

세그먼트 트리를 사용해서 풀었습니다.

쿼리를 2가지 입니다. 특정 인덱스의 값을 바꾸는 것과 특정 구간의 합을 구하는것

update 함수를 통해 특정 인덱스의 값을 변경하였고
query 함수를 통해 특정 구간의 합을 반환하도록 하였습니다.

인덱스는 0 부터 시작하기 때문에 쿼리에서 주어지는 변수를 인덱스로 사용할 경우 -1 을 해주었습니다.