https://www.acmicpc.net/problem/12837
12837번: 가계부 (Hard)
살아있는 화석이라고 불리는 월곡이는 돈에 찌들려 살아가고 있다. 그에게 있어 수입과 지출을 관리하는 것은 굉장히 중요한 문제이다. 스마트폰에 가계부 어플리케이션을 설치해서 사용하려
www.acmicpc.net
[난이도] Gold1
[유형] 세그먼트 트리
[풀이]
세그먼트 트리를 이용하면 됩니다.
#include <cstdio>
using namespace std;
using ll = long long;
int N,Q,sidx;
ll segTree[3000000];
ll sum(int L,int R,int node,int cL,int cR){
if(cR<L || R<cL) return 0;
if(L<=cL && cR<=R) return segTree[node];
int mid = (cL+cR)/2;
return sum(L,R,2*node,cL,mid) + sum(L,R,2*node+1,mid+1,cR);
}
void update(int i,int v){
i+=sidx;
while(i>0){
segTree[i]+=v;
i/=2;
}
}
int main(){
scanf("%d%d",&N,&Q);
for(sidx=1;sidx<N;sidx*=2);
while(Q--){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
if(a==1){
update(b-1,c);
}else{
printf("%lld\n",sum(b-1,c-1,1,0,sidx-1));
}
}
}
https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold1/12837.cpp
'Problem-Solving > BOJ' 카테고리의 다른 글
| [BOJ/백준][Gold4] 16957 : 체스판 위의 공 (C++) (0) | 2021.11.09 |
|---|---|
| [BOJ/백준][Gold3] 1943 : 동전 분배 (C++) (0) | 2021.11.09 |
| [BOJ/백준][Gold4] 1757 : 달려달려 (C++) (0) | 2021.11.09 |
| [BOJ/백준][Gold4] 1749 : 점수따먹기 (C++) (0) | 2021.11.09 |
| [BOJ/백준][Gold4] 1593 : 문자 해독 (C++) (0) | 2021.11.09 |