[12836] 가계부

• 입력: 월곡이가 살아온 날 N, 쿼리의 개수 Q

1 p x : 생후 p일에 x를 추가 (1 ≤ p ≤ N, -109 ≤ x ≤ 109)

2 p q : 생후 p일부터 q일까지 변화한 양  (1 ≤ p ≤ q ≤ N)

• 출력: 각 쿼리에 대한 계산된 값
• 알고리즘: 세그먼트 트리
• 소스코드 
#define _CRT_SECURE_NO_WARNINGS #include <cstdio> #include <vector> #include <cmath> using namespace std; #define ll long long void update(vector<ll>&, int, int, int, int, ll); ll sum(vector<ll>&, int, int, int, int, int); int main() { int N, Q; scanf("%d %d", &N, &Q); int h = (int)ceil(log2(N)); vector<ll> tree(1 << (h + 1), 0); int n, p, q; ll x; for (int i = 0; i < Q; i++) { scanf("%d", &n); switch (n) { case 1: scanf("%d %lld", &p, &x); update(tree, 1, p - 1, 0, N - 1, x); break; case 2: scanf("%d %d", &p, &q); printf("%lld\n", sum(tree, 1, 0, N - 1, p - 1, q - 1)); break; } } return 0; } void update(vector<ll>& tree, int node, int index, int start, int end, ll diff) { if (index < start || index > end) return; tree[node] += diff; if (start != end) { update(tree, node * 2, index, start, (start + end) / 2, diff); update(tree, node * 2 + 1, index, (start + end) / 2 + 1, end, diff); } } ll sum(vector<ll>& tree, int node, int start, int end, int left, int right) { if (left > end || right < start) return 0; if (left <= start && right >= end) return tree[node]; return sum(tree, node * 2, start, (start + end) / 2, left, right) + sum(tree, node * 2 + 1, (start + end) / 2 + 1, end, left, right); }  

구간 합 구하기 문제와 알고리즘이 완전히 같다. 단, 처음 모든 값이 0이기 때문에 별도의 배열이 필요없고 init 함수 또한 필요 없다.

Easy와 Hard의 N, Q의 범위가 다를 뿐 똑같이 성공하였다. 

• 문제참고: https://www.acmicpc.net/problem/12836