Post List

[BOJ] 백준 2042 구간 합 구하기

날짜:
링크 : https://www.acmicpc.net/problem/2042

이 문제는 1백만개의 배열에서  "어떤 부분"의 합을 구하는 문제 입니다.
그리고 m번, 배열에서 값이 바뀌기 때문에 이 문제를 순차적으로 더하는 문제로 접근하게 된다면 시간초과가 일어납니다. n * k = 백만 * 1만 = 100억의 시간(대략 100초).

하지만 이 문제를 세그먼트 트리(구간트리)로 풀게 된다면, 찾는 시간을 logn으로 줄일 수 있게 됩니다. 따라서 이 문제는 세그먼트 트리로 접근하겠습니다.

1. 세그먼트 트리의 생성
세그먼트 트리를 생성하기 위하여 일단 배열을 반으로 계속 쪼개 나갑니다. 그러다가 왼쪽범위와 오른쪽범위가 만나게 되면 그 곳이 해당 재귀함수의 최종역 입니다. 따라서 tree에 num값을 저장해 줍니다.

2. 세그먼트 트리의 업데이트
바뀐 부분만 고쳐주면 됩니다. 하지만 우리는 그 바뀐 부분이, 세그먼트 트리의 어느 부분에 속한지 모르기 때문에 1부터 N까지 전부 확인해봐야 합니다. 다행히도 우리는 바뀌어야 할 부분의 인덱스를 알고 있습니다. 답이 될 수 없는 (non promising) 것들은 빠르게 쳐내줍니다.

3. 세그먼트 트리의 합
첫번째부터 마지막번째까지 트리를 돌며 트리의 값을 더해주면 됩니다.

소스코드 :

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
#include <iostream>
#include <vector>
#include <list>
#include <string>
#include <queue>
typedef long long ll;
using namespace std;
int n, m, k;
ll num[1000001]{ 0, };
ll tree[1000001 * 4]{ 0, };
ll Min(ll a, ll b) {
    if (a > b) {
        return b;
    }
    else return a;
}
ll Init(int node, int start, int end) {
    if (start == end) {
        return tree[node] = num[start];
    }
    ll mid = (start + end) / 2;
    ll left = Init(2 * node, start, mid);
    ll right = Init(2 * node + 1, mid + 1, end);
    return tree[node] = left + right;
}
ll update(int index, int newValue, int node, int start, int end) {
    if (index < start || end < index) {
        return tree[node];
    }
    if (start == end)
        return tree[node] = newValue;
    int mid = (start + end) / 2;
    ll left = update(index, newValue, node * 2, start, mid);
    ll right = update(index, newValue, node * 2 + 1, mid + 1, end);
    return tree[node] = left + right;
}
ll Sum(int left, int right, int node, int start, int end) {
    if (left <= start && end <= right) {
        
        return tree[node];
    }
    if (right < start || end < left) {
        return 0;
    }
    int mid = (start + end) / 2;
    return Sum(left, right, node * 2, start, mid) + Sum(left, right, node * 2 + 1, mid + 1, end);
}
int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++) {
        cin >> num[i];
    }
    // Initiating of seg tree.
    Init(1, 1, n);
    for (int i = 1; i <= m + k; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        
        if (a == 1) {
            update(b, c, 1, 1, n);
        }
        else {
            cout << Sum(b, c, 1, 1, n) << '\n';
        }
    }
}
cs

댓글

댓글 쓰기