가계부(백준12837)

• 전형적인 세그먼트 트리 문제이다
• 특정 날짜에 대한 수입 혹은 지출을 입력으로 받을 때 유의해야 한다. 배열의 값을 아예 변경하면 안 되고 변화량을 더해야 한다. 

import sys 
input = sys.stdin.readline 
n,q =map(int, input().split())
tree = [0 for _ in range((4*n)+1)]
arr = [0 for _ in range(n+1)]

def change(idx, s,e,place, value):
    if place < s or place> e :
        return 
    if s==e :
        tree[idx]=arr[s]
        return 
    mid= (s+e)//2
    change(idx*2, s,mid,place, value) 
    change(idx*2+1, mid+1,e,place,value)
    tree[idx] = tree[idx*2]+ tree[idx*2+1] 
    
    
def find(idx,s,e,left,right):
    if ( e <left or right < s):
        return 0 
    if (left <= s and e <= right ):
        return tree[idx] 
    mid = (s+e)//2 
    return find(idx*2,s,mid,left,right)+find(idx*2+1,mid+1,e,left,right) 
    
        
for i in range(q):
    a,b,c =map(int, input().split())
    if a ==1 :   # 지출 변화를 추가 
        arr[b] += c 
        change(1,1,n,b,c)
    else : # b~ c 까지의 지출변화 
        print(find(1,1,n,b,c))