[ BOJ 백준 12837 - 가계부 (Hard) ] 해설 및 코드

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

 

목적

생후 p일에 수입/지출을 기록하고, p~q의 변화량을 구하자.

 

접근법

1. 세그먼트 트리로 구현한다.(참고, 백준 2042 - 구간 합 구하기)

 

#include<bits/stdc++.h>
#define f(i,l,r) for(int i=l;i<=r;++i)
#define fr(i,l,r) for(int i=l;i>=r;--i)
using namespace std;
typedef long long ll;
 
int N,Q,offset;
ll s[1<<21]{};
 
void update(int p,int x){
    s[p+=offset]+=x;
    while(p>>=1)s[p]+=x;
}
 
void print(int p,int q){
    p+=offset;q+=offset;
    ll ans=0;
    while(p<=q){
        if(p&1)ans+=s[p++];
        if(!(q&1))ans+=s[q--];
        p>>=1;q>>=1;
    }
    cout<<ans<<'\n';
}
 
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin>>N>>Q;
    
    offset=1;
    while(offset<N)offset<<=1;
    --offset;
    
    while(Q--){
        int op,a,b;cin>>op>>a>>b;
        if(op==1)update(a,b);
        else print(a,b);
    }
    
    return 0;
}
 

 

 

문제 설명과 코드에 대한 피드백은 언제나 환영합니다.

 다양한 의견 댓글로 남겨주세요.