[1275번] 커피숍2

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

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

세그먼트 트리를 이용하여 구간 합 구현을 할 수 있다면 사실 풀고도 남는 문제이다.

이 문제는 함정이 하나 있는데, 1~5의 구간 합을 구해달라 할 수 있지만, 5~1의 구간 합을 구해달라 할 수도 있다.  

그러기에 swap 매크로 함수를 이용하여 left가 right보다 클 때는 swap을 해주어 원래 구하는 방식대로 나타나게 해준다.

그리고 이 문제와 동일한 함정 문제는 다음과 같다.

[2268번] 수들의 합 :: https://www.acmicpc.net/problem/2268

소스 코드 : 

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 75 76 77 78 79 80 81

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

Crocus