반응형

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

 

12837번: 가계부 (Hard)

살아있는 화석이라고 불리는 월곡이는 돈에 찌들려 살아가고 있다. 그에게 있어 수입과 지출을 관리하는 것은 굉장히 중요한 문제이다. 스마트폰에 가계부 어플리케이션을 설치해서 사용하려

www.acmicpc.net

 

 

[ 문제풀이 ]

이 문제를 풀기 전에 다음 글을 먼저 읽고 오시는 것을 추천드립니다.

https://rudalsd.tistory.com/51

 

[ 자료구조 ] 세그먼트 트리 (Segment Tree)

1. 세그먼트 트리 (Segment Tree) 먼저, 세그먼트 트리가 무엇인지 알아봅시다! 세그먼트 트리는 구간 합을 저장하기 위한 트리입니다. 예를 들어 size가 5인 배열이 있다고 생각해봅시다. int arr [5] = {1

rudalsd.tistory.com

 

1. 총합이 int형 범위를 벗어나므로 long long형으로 저장합니다.

 

[ 소스코드 ]

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
#include<iostream>
#define ll long long
 
using namespace std;
 
int N, Q;
ll segTree[2100000];
 
ll sumTree(int node, int start, int end, int sidx, int eidx)
{
    if (end < sidx || start > eidx) return 0;
    if (sidx <= start && end <= eidx) return segTree[node];
 
    int mid = (start + end) / 2;
    ll left = sumTree(node * 2, start, mid, sidx, eidx);
    ll right = sumTree(node * 2 + 1, mid + 1, end, sidx, eidx);
 
    return left + right;
}
 
void modifyTree(int node, int start, int end, int idx, ll x)
{
    if (idx < start || idx > end) return;
    segTree[node] += x;
 
    if (start != end) {
        int mid = (start + end) / 2;
        modifyTree(node * 2, start, mid, idx, x);
        modifyTree(node * 2 + 1, mid + 1, end, idx, x);
    }
}
 
int main()
{
    scanf("%d %d", &N, &Q);
 
    for (int i = 0; i < Q; i++) {
        int n, p, q;
        scanf("%d %d %d", &n, &p, &q);
 
        if (n == 1) {
            modifyTree(1, 1, N, p, q);
        }
        else {
            printf("%lld\n", sumTree(1, 1, N, p, q));
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 3745번 - 오름 (C++)  (0) 2023.01.03
[ 백준 ] 14438번 - 수열과 쿼리 17 (C++)  (0) 2023.01.02
[ 백준 ] 17244번 - 아맞다우산 (C++)  (0) 2022.12.31
[ 백준 ] 17497번 - 계산 (C++)  (0) 2022.12.30
[ 백준 ] 2268번 - 수들의 합 7 (C++)  (0) 2022.12.29
반응형

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

 

2268번: 수들의 합 7

첫째 줄에는 N(1 ≤ N ≤ 1,000,000), M(1 ≤ M ≤ 1,000,000)이 주어진다. M은 수행한 명령의 개수이며 다음 M개의 줄에는 수행한 순서대로 함수의 목록이 주어진다. 첫 번째 숫자는 어느 함수를 사용했는

www.acmicpc.net

 

 

[ 문제풀이 ]

이 문제를 풀기 전에 다음 글을 먼저 읽고 오시는 것을 추천드립니다.

https://rudalsd.tistory.com/51

 

[ 자료구조 ] 세그먼트 트리 (Segment Tree)

1. 세그먼트 트리 (Segment Tree) 먼저, 세그먼트 트리가 무엇인지 알아봅시다! 세그먼트 트리는 구간 합을 저장하기 위한 트리입니다. 예를 들어 size가 5인 배열이 있다고 생각해봅시다. int arr [5] = {1

rudalsd.tistory.com

 

1. 총합이 int형 범위를 벗어나므로 long long형으로 저장합니다.

 

 

[ 소스코드 ]

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
#include<iostream>
#define ll long long
 
using namespace std;
 
int N, M;
ll segTree[2100000];
int arr[1000001];
 
ll sum(int node, int start, int end, int sidx, int eidx)
{
    if (end < sidx || start > eidx) return 0;
    if (sidx <= start && end <= eidx) return segTree[node];
 
    int mid = (start + end) / 2;
    ll left = sum(node * 2, start, mid, sidx, eidx);
    ll right = sum(node * 2 + 1, mid + 1, end, sidx, eidx);
 
    return left + right;
}
 
 
void modify(int node, int start, int end, int idx, int diff)
{
    if (idx < start || idx > end) return;
    segTree[node] += diff;
 
    if (start != end) {
        int mid = (start + end) / 2;
        modify(node * 2, start, mid, idx, diff);
        modify(node * 2 + 1, mid + 1, end, idx, diff);
    }
}
 
int main()
{
    scanf("%d %d", &N, &M);
 
    for (int i = 0; i < M; i++) {
        int a,b,c;
        scanf("%d %d %d", &a, &b, &c);
 
        if (a == 0) {
            if (b < c) {
                printf("%lld\n", sum(1, 1, N, b, c));
            }
            else {
                printf("%lld\n", sum(1, 1, N, c, b));
            }
        }
        else {
            int diff = c - arr[b];
            arr[b] = c;
            modify(1,1,N,b,diff);
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 17244번 - 아맞다우산 (C++)  (0) 2022.12.31
[ 백준 ] 17497번 - 계산 (C++)  (0) 2022.12.30
[ 백준 ] 1194번 - 달이 차오른다, 가자. (C++)  (0) 2022.12.28
[ 백준 ] 2589번 - 보물섬 (C++)  (0) 2022.12.27
[ 백준 ] 23793번 - 두 단계 최단 경로 1 (C++)  (0) 2022.12.26
반응형

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

 

14428번: 수열과 쿼리 16

길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i v : Ai를 v로 바꾼다. (1 ≤ i ≤ N, 1 ≤ v ≤ 109) 2 i j : Ai, Ai+1, ..., Aj에서 크기가 가장 작은 값의

www.acmicpc.net

 

 

[ 문제풀이 ]

 

이 문제를 풀기 전에 다음 글을 읽고 오시면 좋습니다!!

https://rudalsd.tistory.com/51?category=1073064 

 

[ 자료구조 ] 세그먼트 트리 (Segment Tree)

1. 세그먼트 트리 (Segment Tree) 먼저, 세그먼트 트리가 무엇인지 알아봅시다! 세그먼트 트리는 구간 합을 저장하기 위한 트리입니다. 예를 들어 size가 5인 배열이 있다고 생각해봅시다. int arr [5] = {1

rudalsd.tistory.com

 

이 문제는 가장 작은 수의 인덱스를 출력해야 하는 문제이기 때문에 node struct를 만들어서 숫자와 인덱스를 저장합니다. 나머지는 다른 세그먼트 트리와 같은 방식으로 풀어주면 됩니다.

 

[ 소스 코드 ]

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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
#include<iostream>
#include<vector>
#include<cmath>
 
using namespace std;
 
struct node {
    int num;
    int idx;
};
 
int N, M;
int arr[100001];
vector<node> segTree;
 
node makeTree(int cur, int start, int end)    //세그먼트 트리 만들기
{
    int mid = (start + end) / 2;
    if (start == end) {
        return segTree[cur] = { arr[start], start };
    }
 
    node left = makeTree(cur * 2, start, mid);    //왼쪽 자식 노드
    node right = makeTree(cur * 2 + 1, mid + 1, end);    //오른쪽 자식 노드
 
    if (left.num < right.num) {
        return segTree[cur] = { left.num, left.idx };
    }
    else if (right.num < left.num) {
        return segTree[cur] = { right.num, right.idx };
    }
    else {
        if (left.idx < right.idx) {
            return segTree[cur] = { left.num, left.idx };
        }
        else {
            return segTree[cur] = { right.num, right.idx };
        }
    }
}
 
node updateTree(int cur, int start, int end, int idx)    //세그먼트 트리 업데이트
{
    if (idx < start || idx > end) {        //start ~ end에 idx가 포함되어 있지 않을 때
        return segTree[cur];
    }
    if (start == end) {        //바꿀 숫자의 idx에 도착했을 때
        return segTree[cur] = { arr[start], start };
    }
 
    int mid = (start + end) / 2;
    node left = updateTree(cur * 2, start, mid, idx);    //왼쪽 자식 노드
    node right = updateTree(cur * 2 + 1, mid + 1, end, idx);    //오른쪽 자식 노드
 
    if (left.num < right.num) {
        return segTree[cur] = { left.num, left.idx };
    }
    else if (right.num < left.num) {
        return segTree[cur] = { right.num, right.idx };
    }
    else {
        if (left.idx < right.idx) {
            return segTree[cur] = { left.num, left.idx };
        }
        else {
            return segTree[cur] = { right.num, right.idx };
        }
    }
}
 
node minTree(int cur, int start, int end, int sidx, int eidx)    //최솟값 구하기
{
    if (end < sidx || start > eidx) {    //범위를 완전히 벗어났을 때
        return { 1111111111, 987654321 };
    }
    if (sidx <= start && eidx >= end) {    //범위에 완전히 포함될 때
        return segTree[cur];
    }
    //범위에 일부 포함될 때
    int mid = (start + end) / 2;
 
    node left = minTree(cur * 2, start, mid, sidx, eidx);
    node right = minTree(cur * 2 + 1, mid + 1, end, sidx, eidx);
 
    if (left.num < right.num) {
        return left;
    }
    else if (right.num < left.num) {
        return right;
    }
    else {
        if (left.idx < right.idx) {
            return left;
        }
        else {
            return right;
        }
    }
}
 
int main()
{
    cin >> N;
 
    for (int i = 1; i <= N; i++) {
        scanf("%d", &arr[i]);
    }
 
    int size = (1 << (int)(ceil(log2(N) + 1)));
    segTree.resize(size);
    makeTree(1, 1, N);
 
    cin >> M;
 
    for (int i = 0; i < M; i++) {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
 
        if (a == 1) {
            arr[b] = c;
            updateTree(1, 1, N, b);
        }
        else {
            node ans = minTree(1, 1, N, b, c);
            printf("%d\n", ans.idx);
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 1086번 - 박성원 (C++)  (0) 2022.07.15
[ 백준 ] 17371번 - 이사 (C++)  (0) 2022.07.14
[ 백준 ] 13977번 - 이항 계수와 쿼리 (C++)  (0) 2022.07.12
[ 백준 ] 11689번 - GCD(n, k) = 1 (C++)  (0) 2022.07.11
[ 백준 ] 3015번 - 오아시스 재결합 (C++)  (0) 2022.07.10
반응형

1. 세그먼트 트리 (Segment Tree)

 

먼저, 세그먼트 트리가 무엇인지 알아봅시다! 세그먼트 트리는 구간 합을 저장하기 위한 트리입니다. 예를 들어 size가 5인 배열이 있다고 생각해봅시다. int arr [5] = {1,2,3,4,5} 일 때, 다음과 같은 그래프로 나타낼 수 있습니다.

 

 

각각의 노드들의 값은 자식 노드들의 값들을 더한 것입니다. 구간의 합을 구할 때 보통 O(N)의 시간이 걸리지만 세그먼트 트리를 이용한다면 O(logN)의 시간만에 값을 구할 수 있습니다.

 

트리를 만들기 위해서는 트리의 높이를 알아야 합니다. 트리의 높이를 알기 위해서는 리프노드의 수를 이용해야 하고, 다음과 같이 구할 수 있습니다.

 

트리의 높이 = ceil(log(N))

 

ceil은 어떤 수든 올림을 해서 구해주는 함수입니다. 따라서 log5 = 2.xxx이지만 ceil함수 안에 넣는다면 3이라는 수가 나오게 됩니다. 위의 그래프를 보면 루트 노드의 높이를 0이라고 했을 때 트리의 높이가 3인 것을 알 수 있습니다. 따라서 세그먼트 트리의 크기는 2^(트리의 높이 + 1)이 됩니다.

 

2. 세그먼트 트리 만들기

 

먼저 주어진 범위를 반으로 나누고, 나누어진 2개의 범위에 대해서 왼쪽과 오른쪽 범위에 대해 각각 재귀호출을 해줍니다. 이를 계속 반복해주다가 리프 노드에 다다르면 재귀를 멈춰주시면 됩니다.

 

이진트리이므로 항상 범위를 반으로 나누면 됩니다. 즉 (현재 노드, 시작 범위, 끝 범위)의 형태로 반복해서 재귀 호출을 해주고 마지막에 시작 범위와 끝 범위가 일치할 때가 리프 노드이므로 값을 넣어주고 그 값을 return 해주면 됩니다.

 

 

3. 세그먼트 트리 구간합 구하기

 

구간합을 구할 때 조건을 나누어 주면 쉽게 구할 수 있습니다. 

 

1. 현재 탐색하는 범위가 찾고자하는 범위와 완전히 겹치는 경우

2. 현재 탐색하는 범위가 찾고자하는 범위와 일부 겹치는 경우

3. 현재 탐색하는 범위가 찾고자하는 범위와 완전히 겹치지 않는 경우

 

이를 코드로 표현하면 다음과 같습니다.

 

 

4. 세그먼트 트리 값 바꾸기

 

특정 index의 값을 바꿀 때도 분기를 나누어서 구해주면 됩니다. 바꾸고자 하는 index가 현재 범위에 포함되어 있는지 없는지만 체크해주면 쉽게 구현할 수 있습니다.

 

 

반응형
저작자표시 비영리 변경금지 (새창열림)

'자료구조' 카테고리의 다른 글

[ 자료구조 ] 머지 소트 트리(Merge Sort Tree)  (0) 2023.08.07
[ 자료구조 ] 트라이(Trie)  (0) 2023.06.24
[ 자료구조 ] 비재귀 세그먼트 트리 (Segment Tree)  (0) 2023.05.04
[ 자료구조 ] 느리게 갱신되는 세그먼트 트리 (Lazy Propagation)  (0) 2023.01.16
[ 자료구조 ] 희소 배열(Sparse Table)  (0) 2022.08.07

+ Recent posts

티스토리툴바