Beads (백준 11143)

트리의 업데이트 함수를 만들 때 조금 어렵다.

 

  1) 변경해야 하는 위치가 먼저 찾는 범위(s와 e 사이)에 없는 경우 빨리 함수를 종료 시킨다. 

  2) 1)의 조건을 통과하면 해당 tree의 값을 업데이트 해준다. 

  3) s와 e가 같으면 이미 제일 밑바닥의 tree에 있음으로 종료시킨다. 

  4) 왼쪽 tree, 오른쪽 tree를 또 업데이트 한다. 

import sys 
input =sys.stdin.readline 
t= int(input()) # 전체 테스트케이스 

def change(idx,s,e,p, val):
    if ((p < s) or (e < p)) :
        return 
    tree[idx] += val 
    
    if s==e :
        return 
    mid= (s+e)//2
    change(idx*2 , s, mid, p, val)
    change(idx*2+1, mid+1, e, p, val)
   

def find(idx,s,e,l,r):
    if( (e<l ) or (r< s)):
        return 0 
    if(l <= s and e <=r):
        return tree[idx]
        
    mid= (s+e)//2 
    l1= find(idx*2, s,mid, l,r)
    r1= find(idx*2+1,mid+1,e,l,r)
    return l1+ r1 
    
        
    





for _ in range(t):
    b,p,q =map(int, input().split())
    arr =[0 for _ in range(b+1)]
    tree =[0 for _ in range((4*b)+1)]
    for i in range(p+q):
        x,y,z= map(str, input().split())
        y = int(y)
        z = int(z)
        
        if x =="P":
            arr[y] +=  z 
            change(1,1,b,y,z)
            
        else :
            if y==z :
                print(arr[y])
            else :
                print(find(1,1,b,y,z))