반응형

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

+ Recent posts

티스토리툴바