백준 12837번 가계부 (Hard)[C++]

1. 문제 풀이

 오늘 풀어본 문제는 백준 12837번 가계부 (Hard)입니다. 문제의 유형은 세그먼트 트리입니다. 세그먼트 트리는 리프 노드의 값을 변경하는 갱신 연산과 어떤 구간이 주어졌을 때, 그 구간의 합을 구하는 쿼리 연산이 있습니다. 이 두 연산을 단순하게 사용하기만 하면 AC를 받을 수 있는 문제이므로 세그먼트 트리에 대해서 공부하고 구현도 해보았다면 연습 문제로 풀어보기 좋은 문제 같습니다. 주의할 점은 갱신 연산을 할 때, 값을 바꾸는 것이 아니라 + 연산을 해야 한다는 점입니다.

2. 코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> pi; typedef pair<ll, ll> pl;
typedef tuple<int, int, int> ti; typedef tuple<ll, ll, ll> tl; typedef vector<int> vi; typedef vector<ll> vl;
typedef vector<pi> vpi; typedef vector<pl> vpl; typedef vector<ti> vti; typedef vector<tl> vtl;
typedef vector<string> vs; typedef vector<bool> vb; typedef queue<int> qi; typedef queue<ll> ql;
typedef queue<pi> qpi; typedef queue<pl> qpl; typedef queue<ti> qti; typedef queue<tl> qtl;
#define fastio(x, y) cin.tie((x))->sync_with_stdio((y))
#define X first
#define Y second
#define pb push_back
#define sz(x) (int((x).size()))
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
const char nl = '\n';

int n, q;
ll tree[2'000'005];

void update(int p, ll val){
  p += n;
  tree[p] += val;
  for(int i = p; i > 1; i>>=1) tree[i>>1] = tree[i] + tree[i^1];
}

ll query(int l, int r){
  ll ret{};
  for(l += n, r += n; l < r; l>>=1, r>>=1){
    if(l&1) ret += tree[l++];
    if(r&1) ret += tree[--r];
  }
  return ret;
}

int main() {
  fastio(nullptr, false);
  cin >> n >> q; 
  while(q--){
    ll cmd, p, x;
    cin >> cmd >> p >> x;
    if(--cmd) cout << query(p-1, x) << nl;
    else update(p-1, x);
  }
}

 

3. 제출 결과