백준 12837번 가계부 (Hard) 문제풀이(C++)

백준 12837번 가계부 (Hard)

아이디어

첫 번째는 월곡이의 생후 p일에 수입/지출 내용을 추가하는 것이다.

두 번째는 월곡이의 생후 p일부터 q일까지 잔고가 변화한 값을 구하고 출력하는 것이다.

내용 추가 + p ~ q까지의 변화한 값 구하기 -> 누적합
단 범위가 106까지 => 누적합 => 펜윅트리, 세그먼트 트리

세그먼트 트리 : 구현 어려움 + 메모리 큼 + 시간이 오래 걸림
펜윅 트리 : 구현 쉬움 + 메모리 비교적 작음 + 시간이 적게 걸림

∴ 펜윅트리 사용

※주의 할 점
내용을 추가하는 것이지 변화한것이 아니다.
이 것을 모르고 두 번 나가리 당했다

문제풀이

#include<bits/stdc++.h>
using namespace std;
#define MAX 1'000'000 + 10
typedef long long ll;
ll day[MAX];
int n, Q;
void update(int idx, int diff) {
    while (idx <= n + 1) {
        day[idx] += diff;
        idx += (idx & -idx);
    }
}
ll sum(int idx) {
    ll _sum = 0;
    while (idx) {
        _sum += day[idx];
        idx -= (idx & -idx);
    }
    return _sum;
}
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> n >> Q;
    while (Q--) {
        int what; cin >> what;
        if (what == 1) {
            int p, x; cin >> p >> x;
            update(p, x);
        }
        else {
            int p, q; cin >> p >> q;
            cout << sum(q) - sum(p - 1) << '\n';
        }
    }
    return 0;
}