백준/ Gold 1 문제 , 백준 파이썬 12837 , 가계부 (Hard) [세그먼트 트리]

백준/ Gold 1 문제 , 백준 파이썬 12837 , 가계부 (Hard)  [세그먼트 트리]

 

 

풀이 시간

 

Check Point !   ( 해당사항 ✓체크 )

1. 막힘 없이 수월하게 풀린 문제인가?

2. 1시간이내로 풀렸던 문제인가?

3. 1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가?

4. 시간을 써도 도무지 풀 수 없는 문제인가?

5. 솔루션을 찾아봤는가?

-------------------------------------------------------------------------------------------
난이도 체감
1. 최상
2. 상
3. 중
4. 하


<이해도>
1. 완벽히 이해
2. 다소 헷갈리는 부분들이 있음
3. 이해 못함


<덧붙일 말>

 

문제 출처

https://www.acmicpc.net/problem/12837

12837번: 가계부 (Hard)

 

풀이

 

1. 생일을 추가해주는 함수

 

 

2. 변화한 양을 계산해주는 함수

 

 

3. 입력 받기 및 각 함수 호출

 

 

정답

import sys
input=sys.stdin.readline

def update(start,end,index,w,v):
    if w<start or w>end:
        return
    tree[index]+=v
    if start==end:
        return
    mid=(start+end)//2
    update(start,mid,index*2,w,v)
    update(mid+1,end,index*2+1,w,v)

def dayChange(start,end,index,left,right):
    if left>end or right<start:
        return 0
    if left<=start and right>=end:
        return tree[index]
    mid=(start+end)//2
    return dayChange(start,mid,index*2,left,right)+dayChange(mid+1,end,index*2+1,left,right)

N,Q=map(int,input().split())
arr=[0]*N
tree=[0]*(N*4)

for i in range(Q):
    a,b,c=map(int,input().split())
    if a==1:
        arr[b-1]=c
        update(0,N-1,1,b-1,c)
    elif a==2:
        print(dayChange(0,N-1,1,b-1,c-1))