백준 알고리즘 12837번 : 가계부 (Hard)

링크

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

문제

살아있는 화석이라고 불리는 월곡이는 돈에 찌들려 살아가고 있다. 그에게 있어 수입과 지출을 관리하는 것은 굉장히 중요한 문제이다. 스마트폰에 가계부 어플리케이션을 설치해서 사용하려 했지만, 월곡이는 굉장히 오래 살았기에 원하는 정보를 얻기에는 동작 속도가 너무나도 느렸다. 가끔 입력을 빼먹은 것이 생기면 다시 추가하고 계산하는 것도 느려서, 성격이 급한 월곡이는 결국 스마트폰을 부숴버리고 말았다. 월곡이를 도와주는 프로그램을 작성하기 위해, 아래와 같은 동작들을 처리하는 프로그램을 작성하시오.

작성될 가계부 프로그램은 두 가지 동작을 처리해야 한다. 첫 번째는 월곡이의 생후 p일에 수입/지출 내용을 추가하는 것이다. 수입은 양수, 지출은 음수의 형태로 입력이 들어온다. 두 번째는 월곡이의 생후 p일부터 q일까지 잔고가 변화한 값을 구하고 출력하는 것이다. 월곡이가 빚을 지고 있을 수도 있기에 어떤 i에 대해서 생후 i일의 잔고는 음수일 수 있다.

입력

첫째 줄에 월곡이가 살아온 날 N, 쿼리의 개수 Q가 주어진다. (N ≤ 106, Q ≤ 105)

둘째 줄부터 Q+1번째 줄까지는 아래와 같은 형식의 쿼리가 주어진다.

• 1 p x : 생후 p일에 x를 추가한다. (1 ≤ p ≤ N, -109 ≤ x ≤ 109)
• 2 p q : 생후 p일부터 q일까지 변화한 양을 출력한다. (1 ≤ p ≤ q ≤ N)

출력

각 2 쿼리에 대해 계산된 값을 각 줄에 출력한다.

예제 입력 및 출력

풀이 코드(C++)

#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#define X first
#define Y second
#define pb push_back
#define sz(a) int((a).size())
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define MAX(a, b) (((a) > (b)) ? (a) : (b))
#define all(v) v.begin(), v.end()
using namespace std;
using ll = long long;
using ull = unsigned long long;
using dbl = double;
using ldb = long double;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using vi = vector<int>;
using wector = vector<vector<int>>;
using tii = tuple<int,int,int>;

template<typename T = int64_t, size_t sz = 17, typename F = plus<T>>
struct SegTree {
	vector<T> tree; T t; F f{};
	SegTree(T t = T()) : tree(1 << sz + 1, t), t(t) {}
	explicit SegTree(T t, const F& f) : tree(1 << sz + 1, t), t(t), f(f) {}
	
	void Init() {
    for (int i = (1 << sz) - 1; i; i--) {
      tree[i] = f(tree[i << 1], tree[i << 1 | 1]);
    }
  }

	void Update(int i, T val) {
		--i |= 1 << sz; tree[i] += val;
		while (i >>= 1) tree[i] = f(tree[i << 1], tree[i << 1 | 1]);
	}
	T Query(int l, int r) {
		T L = t, R = t; --l |= 1 << sz, --r |= 1 << sz;
		while (l <= r) {
			if (l & 1) L = f(L, tree[l++]);
			if (~r & 1) R = f(tree[r--], R);
			l >>= 1, r >>= 1;
		}
		return f(L, R);
	}
};

SegTree ST;

int main() {
  fastio;
  int n,m; cin >> n >> m;
  ST.Init();
  while(m--){
    int q,p,x; cin >> q >> p >> x;
    if(q == 1) ST.Update(p, x);
    else cout << ST.Query(p, x) << "\n";
  }
  return 0;
}

값을 변경하는 것이 아닌... 추가이기 때문에 +를 해주어야합니다...
이것때문에 계속 틀렸었네요;;