백준 12837 - 가계부 (Hard)

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

 

가계부에 내용이 계속 변하고 $10^{5}$개의 질의를 처리해야 하므로 세그먼트 트리를 사용한다.

 

수입, 지출이 바뀌는 것이 아니라 추가되는 것이므로 갱신 연산을 수행할 때 이에 유의하도록 한다.

 

전체 코드

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
int n, q;

ll ar[1000001];

inline int mid(int stt, int end) { return stt + (end - stt) / 2; }

void update(vector<ll> &tree, int node, int start, int end, int idx, ll diff)
{
    if (idx > end || idx < start) return;
    tree[node] += diff;
    if (start != end)
    {
        int m = mid(start, end);
        update(tree, node * 2, start, m, idx, diff);
        update(tree, node * 2 + 1, m + 1, end, idx, diff);
    }
}

ll sum(vector<ll> &tree, int node, int start, int end, int l, int r)
{
    if (start > r || end < l) return 0;
    if (l <= start && end <= r) return tree[node];
    int m = mid(start, end);
    return sum(tree, node * 2, start, m, l, r) + sum(tree, node * 2 + 1, m + 1, end, l, r);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> q;
    vector<ll> segtree(n * 4);

    while (q--)
    {
        int a, b, c;
        cin >> a >> b >> c;

        if (a == 1)
        {
            ar[b] = c;
            update(segtree, 1, 1, n, b, c);
        }
        else
        {
            cout << sum(segtree, 1, 1, n, b, c) << '\n';
        }
    }
}