[12837번] 가계부 (Hard)

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 세그먼트 트리(Segment Tree) :: http://www.crocus.co.kr/648

2. 자료형

구간 합을 구하는 방식과 같다.

단지 주의해야 할 사항은 query의 반환이 long long형임을 알아야 한다.

왜냐면 최대 입력이 10억이기에 10억이 3번만 반복되도 int형에서 overflow가 나기 때문이다.

또한 구간 합을 구하는 세그먼트 트리와 차이점이 있다면 init없이 update로 모든 행동을 하고있다.

init은 시작하자마자 arr 배열이 주어지면 init을 이용하고, 값이 하나씩 주어질 때는 update를 이용하여 해결할 수 있다.

소스 코드 : 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74

#include <iostream> #include <cstdio> #include <math.h> #include <vector>   using namespace std;   typedef long long ll;   void update(vector<ll> &tree, int node, int start, int end, int index, int val) {     if (!(start <= index && index <= end))         return;       tree[node] += val;       if (start != end)     {         int mid = (start + end) / 2;           update(tree, node * 2, start, mid, index, val);         update(tree, node * 2 + 1, mid + 1, end, index, val);     } }   ll query(vector<ll> &tree, int node, int start, int end, int left, int right) {     if (left > end || right < start)         return 0;       if (left <= start && end <= right)         return tree[node];          int mid = (start + end) / 2;       return query(tree, node * 2, start, mid, left, right) + query(tree, node * 2 + 1, mid + 1, end, left, right); }   int main() {     int n, q;       scanf("%d %d", &n, &q);       int h = (int)ceil(log2(n));     int tree_size = (1 << (1 + h));       vector<ll> tree(tree_size);       while (q--)     {         int num;                  scanf("%d", &num);           if (num == 1)         {             int pos, val;             scanf("%d %d", &pos, &val);             update(tree, 1, 0, n - 1, pos - 1, val);         }         else if (num == 2)         {             int left, right;             scanf("%d %d", &left, &right);             printf("%lld\n", query(tree, 1, 0, n - 1, left - 1, right - 1));         }     }          return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus