(C++) - 백준(BOJ) 12837번 : 가계부 (Hard)

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

12837번: 가계부 (Hard)

segment tree문제였습니다.

 

 

 

📕 풀이방법

 

📔 입력 및 초기화

 기존의 값들은 모두 0에서 출발하므로 init을 만들 필요가 없습니다. 따라서 쿼리의 개수만큼 a,b,c라는 변수에 입력받습니다.

 

 

📔 풀이과정

 1. a==1 이면 update함수를 수행합니다. 이는 변화값을 따로 계산해서 그 차이만큼만 해당하는 구간에 더해주는 것이 아니며 그저 더해주기만 하면 됩니다.

 

 2. a==2이면 b ~ c까지의 구간합을 구해 출력해줍니다.

 

📔 정답출력

a == 2일 경우에만 해당하는 구간 (b ~ c)를 출력해줍니다.

 

---

 

 

📕 Code

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
using ll = long long;
ll days[1000001], tree[4000001], q, n;

void update(int start, int end, int node, int index, int diff){
    if(index < start || index > end) return;
    tree[node] += diff;
    if(start == end) return;
    int mid = (start + end) / 2;
    update(start, mid, node * 2, index, diff);
    update(mid + 1, end, node * 2 + 1, index, diff);
}

ll sum(int start, int end, int node, int left, int right){
    if(end < left || right < start) return 0;
    if(left <= start && end <= right) return tree[node];
    int mid = (start + end) / 2;
    return sum(start, mid, node * 2, left, right) + sum(mid + 1, end, node * 2 + 1, left, right);
}

int main(){
    fastio;
    cin >> n >> q;
    while(q--) {
        ll a,b,c;
        cin >> a >> b >> c;
        if(a == 1) update(1,n,1,b,c);            
        else cout << sum(1,n,1,b,c) << '\n';
    }
}