반응형

문제 출처 :


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



알고리즘 분석 :


문제 해결에 필요한 사항

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


세그먼트 트리의 구간 합 구하는 방식에 대해 이해를 하면 바로 해결할 수 있는 문제이다.


http://www.crocus.co.kr/648에 세그먼트 트리를 이용한 구간 합 구하는 방식을 자세히 기술해 두었으므로


설명은 생략하도록 한다.



소스 코드 : 


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
82
83
84
85
86
87
88
89
90
91
92
#include <cstdio>
#include <iostream>
#include <math.h>
#include <vector>
 
using namespace std;
 
typedef long long ll;
 
ll init(vector<ll> &arr, vector<ll> &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);
}
 
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)
    {
        int mid = (start + end) / 2;
        update(tree, node * 2, start, mid, index, diff);
        update(tree, node * 2 + 1, mid + 1, end, index, 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 && end <= right)
        return tree[node];
 
    int mid = (start + end) / 2;
    return sum(tree, node * 2, start, mid, left, right) + sum(tree, node*2+1, mid+1, end, left, right);
}
int main()
{
    int n, m, k;
    scanf("%d %d %d", &n, &m, &k);
 
    int h = (int)ceil(log2(n));
    int tree_size = (1 << (h+1));
 
    vector<ll> arr(n); 
    vector<ll> tree(tree_size);
 
    for (int i = 0; i < n; i++)
        scanf("%lld", &arr[i]);
        
    init(arr, tree, 1, 0, n - 1);
 
    m += k;
 
    while (m--)
    {
        int get;
        scanf("%d", &get);
 
        if (get == 1)
        {
            int pos;
            ll val;
            scanf("%d %lld", &pos, &val);
            ll diff = val - arr[pos - 1];
            arr[pos - 1] = val;
            update(tree, 1, 0, n - 1, pos - 1, diff);
        }
 
        else if (get == 2)
        {
            int left, right;
            scanf("%d %d", &left, &right);
            printf("%lld\n", sum(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


반응형
저작자표시 비영리 변경금지

'Applied > 알고리즘 문제풀이' 카테고리의 다른 글

[2357번] 최소값과 최대값  (0) 2017.03.13
[11505번] 구간 곱 구하기  (0) 2017.03.12
[2251번] 물통  (0) 2017.03.06
[1149번] RGB거리  (0) 2017.03.06
[2644번] 촌수계산  (0) 2017.03.06

티스토리툴바