[6081번] Hay Expenses

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 세그먼트 트리 :: http://www.crocus.co.kr/648

이 문제는 세그먼트 트리로 문제를 해결 할 수 있다.

구간에 대한 정답을 계속해서 받아내고 싶어하기에 구간 합을 모두 저장해두고 그에따른 쿼리를 찍어내면 된다.

힌트를 보자.

Days:      1 2  3  4 
Counts:    5 8 12  6

query 1..3:  5 + 8 + 12 = 25
query 2..4:  8 + 12 + 6 = 26

결국 이 과정에서 확인해달라는 내용을 init 함수와 query(sum) 함수로 나타낼 수 있다.

세그먼트 트리 중 기초에 해당하는 문제이므로 위 링크의 세그먼트 트리 개념 설명으로 충분하다고 생각이 든다.

소스 코드 : 

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

#include <iostream> #include <cstdio> #include <vector> #include <cmath>   using namespace std;   int init(vector<int> &arr, vector<int> &tree, int node, int start, int end) {     if (start == end)         return tree[node] = arr[start];       int mid = (start + end) / 2;       return tree[node] = init(arr, tree, node * 2, start, mid) + init(arr, tree, node * 2 + 1, mid + 1, end); }   int query(vector<int> &tree, int node, int start, int end, int left, int right) {     if (start > right || end < left)         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, m;     scanf("%d %d", &n, &m);       int h = (int)ceil(log2(n));     int tree_size = (1 << (h + 1));       vector<int> arr(n + 1);     vector<int> tree(tree_size);       for (int i = 0; i < n; i++)         scanf("%d", &arr[i]);       init(arr, tree, 1, 0, n - 1);       while (m--)     {         int left, right;         scanf("%d %d", &left, &right);         printf("%d\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