반응형

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

 

16975번: 수열과 쿼리 21

길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i j k: Ai, Ai+1, ..., Aj에 k를 더한다. 2 x: Ax 를 출력한다.

www.acmicpc.net

 

 

[ 문제풀이 ]

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

https://rudalsd.tistory.com/256

 

[ 자료구조 ] 느리게 갱신되는 세그먼트 트리 (Lazy Propagation)

https://rudalsd.tistory.com/51 [ 자료구조 ] 세그먼트 트리 (Segment Tree) 1. 세그먼트 트리 (Segment Tree) 먼저, 세그먼트 트리가 무엇인지 알아봅시다! 세그먼트 트리는 구간 합을 저장하기 위한 트리입니다.

rudalsd.tistory.com

 

1. 세그먼트 트리와 lazy값을 저장할 배열을 만듭니다.

 

2. 느리게 갱신되는 세그먼트 트리를 활용하여 Update를 하고 원하는 인덱스의 값을 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
#define ll long long
 
using namespace std;
 
int N, M;
ll arr[100001];
ll segTree[263000];
ll lazy[263000];
 
void makeTree(int node, int start, int end)
{
    if (start == end) {
        segTree[node] = arr[start];
        return;
    }
 
    int mid = (start + end) / 2;
    makeTree(node * 2, start, mid);
    makeTree(node * 2 + 1, mid + 1, end);
 
    segTree[node] = segTree[node * 2] + segTree[node * 2 + 1];
}
 
void modifyLazy(int node, int start, int end)
{
    if (lazy[node] != 0) {
        segTree[node] += (ll)(end - start + 1) * lazy[node];
 
        if (start != end) {
            lazy[node * 2] += lazy[node];
            lazy[node * 2 + 1] += lazy[node];
        }
 
        lazy[node] = 0;
    }
}
 
void modifyTree(int node, int start, int end, int i, int j, ll k)
{
    modifyLazy(node, start, end);
 
    if (start > j || end < i) return;
 
    if (i <= start && end <= j) {
        lazy[node] += k;
        modifyLazy(node, start, end);
 
        return;
    }
 
    int mid = (start + end) / 2;
    modifyTree(node * 2, start, mid, i, j, k);
    modifyTree(node * 2 + 1, mid + 1, end, i, j, k);
 
    segTree[node] = segTree[node * 2] + segTree[node * 2 + 1];
}
 
void getTree(int node, int start, int end, int x)
{
    modifyLazy(node, start, end);
 
    if (start > x || x > end) return;
    if (start == end) {
        arr[start] = segTree[node];
        return;
    }
 
    int mid = (start + end) / 2;
    getTree(node * 2, start, mid, x);
    getTree(node * 2 + 1, mid + 1, end, x);
}
 
int main()
{
    scanf("%d", &N);
 
    for (int i = 1; i <= N; i++) {
        scanf("%lld", &arr[i]);
    }
 
    makeTree(1, 1, N);
 
    scanf("%d", &M);
 
    for (int m = 0; m < M; m++) {
        int cmd;
        scanf("%d", &cmd);
 
        if (cmd == 1) {
            int i, j;
            ll k;
            scanf("%d %d %lld", &i, &j, &k);
            modifyTree(1, 1, N, i, j, k);
        }
        else {
            int x;
            scanf("%d", &x);
            getTree(1, 1, N, x);
 
            printf("%lld\n", arr[x]);
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 1777번 - 순열복원 (C++)  (0) 2023.01.20
[ 백준 ] 1849번 - 순열 (C++)  (0) 2023.01.19
[ 백준 ] 10999번 - 구간 합 구하기 2 (C++)  (0) 2023.01.17
[ 백준 ] 5676번 - 음주 코딩 (C++)  (0) 2023.01.15
[ 백준 ] 18436번 - 수열과 쿼리 37 (C++)  (0) 2023.01.14
반응형

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

 

10999번: 구간 합 구하기 2

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄

www.acmicpc.net

 

 

[ 문제풀이 ]

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

https://rudalsd.tistory.com/256

 

[ 자료구조 ] 느리게 갱신되는 세그먼트 트리 (Lazy Propagation)

https://rudalsd.tistory.com/51 [ 자료구조 ] 세그먼트 트리 (Segment Tree) 1. 세그먼트 트리 (Segment Tree) 먼저, 세그먼트 트리가 무엇인지 알아봅시다! 세그먼트 트리는 구간 합을 저장하기 위한 트리입니다.

rudalsd.tistory.com

 

1. 세그먼트 트리와 lazy값을 저장할 배열을 만듭니다.

 

2. 느리게 갱신되는 세그먼트 트리를 활용하여 Update를 하고 구간 합을 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
#define ll long long
 
using namespace std;
 
int N, M, K;
ll arr[1000001];
ll segTree[2100000];
ll lazy[2100000];    //방문할 필요가 없는 노드의 경우 다음 방문 때 더할 값을 저장
 
void makeTree(int node, int start, int end)
{
    if (start == end) {
        segTree[node] = arr[start];
        return;
    }
 
    int mid = (start + end) / 2;
    makeTree(node * 2, start, mid);
    makeTree(node * 2 + 1, mid + 1, end);
 
    segTree[node] = segTree[node * 2] + segTree[node * 2 + 1];
}
 
void modifyLazy(int node, int start, int end)    //현재 노드에 lazy 값이 있다면 더해주기
{
    if (lazy[node] != 0) {
        segTree[node] += (ll)(end - start + 1) * lazy[node];
        if (start != end) {    //리프 노드가 아니라면 아래 노드에 lazy값 물려주기
            lazy[node * 2] += lazy[node];
            lazy[node * 2 + 1] += lazy[node];
        }
 
        lazy[node] = 0;
    }
}
 
void modifyTree(int node, int start, int end, int sidx, int eidx, ll d)
{
    modifyLazy(node, start, end);    //현재 노드에 lazy값 체크
 
    if (sidx > end || start > eidx) return;
 
    if (sidx <= start && end <= eidx) {    //완전히 포함된다면
        segTree[node] += (ll)(end - start + 1) * d;
        if (start != end) {    //리프 노드가 아닐 경우 아래 노드에 lazy값 물려주기
            lazy[node * 2] += d;
            lazy[node * 2 + 1] += d;
        }
        return;
    }
 
    int mid = (start + end) / 2;
    modifyTree(node * 2, start, mid, sidx, eidx, d);
    modifyTree(node * 2 + 1, mid+1, end, sidx, eidx, d);
 
    segTree[node] = segTree[node * 2] + segTree[node * 2 + 1];
}
 
ll sumTree(int node, int start, int end, int sidx, int eidx)
{
    modifyLazy(node, start, end);    //현재 노드에 lazy값 체크
 
    if (start > eidx || end < sidx) 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;
}
 
int main()
{
    scanf("%d %d %d", &N, &M, &K);
 
    for (int i = 1; i <= N; i++) {
        scanf("%lld", &arr[i]);
    }
 
    makeTree(1, 1, N);
 
    for (int i = 0; i < M + K; i++) {
        int a;
        scanf("%d", &a);
 
        if (a == 1) {
            int b, c;
            ll d;
            scanf("%d %d %lld", &b, &c, &d);
 
            modifyTree(1, 1, N, b, c, d);
        }
        else {
            int b, c;
            scanf("%d %d", &b, &c);
 
            printf("%lld\n", sumTree(1, 1, N, b, c));
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 1849번 - 순열 (C++)  (0) 2023.01.19
[ 백준 ] 16975번 - 수열과 쿼리 21 (C++)  (0) 2023.01.18
[ 백준 ] 5676번 - 음주 코딩 (C++)  (0) 2023.01.15
[ 백준 ] 18436번 - 수열과 쿼리 37 (C++)  (0) 2023.01.14
[ 백준 ] 14427번 - 수열과 쿼리 15 (C++)  (0) 2023.01.13
반응형

https://rudalsd.tistory.com/51

 

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

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

rudalsd.tistory.com

1. 느리게 갱신되는 세그먼트 트리 (Lazy Propagation)

 

Lazy Propagation에서는 각 노드마다 lazy라는 값을 둡다. Lazy Propagation이라는 이름에서 알 수 있듯, 이 자료구조에서는 모든 값을 그때그때 갱신하지 않습니다. 굳이 갱신할 필요가 없는 노드에 대해서 lazy라는 값을 조정해 나중에 이 노드를 방문할 일이 생길 때까지는 갱신을 미루어 시간적 효율을 올리는 것입니다.

 

2. Lazy Propagation 만들기

 

Lazy Propagation을 만드는 방식은 일반적인 세그먼트 트리를 만드는 방식과 똑같습니다.

 

3. Lazy Propagation Update

 

Lazy Propagation에서 값을 수정하는 방법은 다음과 같습니다.

 

Update : 2 - 4 (+10)

Update : 2 - 4 (+10)

Update : 2 - 4 (+10)

Update : 2 - 4 (+10)

Update : 2 - 4 (+10)

Update : 2 - 4 (+10)

이렇게 2-4 구간에 대한 Update는 끝납니다. 일반적인 세그먼트 트리였다면 값이 갱신되는 리프 노드까지 내려갔다가 올라와야 하므로 더 오래 걸리지만 Lazy Propagation을 사용한다면 불필요한 방문을 줄여 훨씬 더 빠르게 갱신이 가능합니다.

 

이후 lazy값이 있는 노드에 방문한다면 노드에 그 값을 적용시키고 아래 노드에 물려줍니다.

 

4. Lazy Propagation 구간합 구하기

 

일반적인 세그먼트 트리와 구간합을 구하는 방식은 동일합니다. 하지만 해당 노드에 lazy값이 있다면 적용시킨 후 값을 더해주면 됩니다.

 

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

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

[ 자료구조 ] 머지 소트 트리(Merge Sort Tree)  (0) 2023.08.07
[ 자료구조 ] 트라이(Trie)  (0) 2023.06.24
[ 자료구조 ] 비재귀 세그먼트 트리 (Segment Tree)  (0) 2023.05.04
[ 자료구조 ] 희소 배열(Sparse Table)  (0) 2022.08.07
[ 자료구조 ] 세그먼트 트리 (Segment Tree)  (0) 2022.07.02

+ Recent posts

티스토리툴바