BOJ_10999_구간 합 구하기 2 (Java)
[Platinum IV] 구간 합 구하기 2 - 10999
성능 요약
메모리: 119644 KB, 시간: 784 ms
분류
세그먼트 트리, 느리게 갱신되는 세그먼트 트리, 자료 구조
제출 일자
2024년 7월 31일 05:05:27
문제 설명
어떤 N개의 수가 주어져 있다. 그런데 중간에 수의 변경이 빈번히 일어나고 그 중간에 어떤 부분의 합을 구하려 한다. 만약에 1,2,3,4,5 라는 수가 있고, 3번째부터 4번째 수에 6을 더하면 1, 2, 9, 10, 5가 되고, 여기서 2번째부터 5번째까지 합을 구하라고 한다면 26을 출력하면 되는 것이다. 그리고 그 상태에서 1번째부터 3번째 수에 2를 빼고 2번째부터 5번째까지 합을 구하라고 한다면 22가 될 것이다.
입력
첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄까지 N개의 수가 주어진다. 그리고 N+2번째 줄부터 N+M+K+1번째 줄까지 세 개의 정수 a, b, c 또는 a, b, c, d가 주어지는데, a가 1인 경우 b번째 수부터 c번째 수에 d를 더하고, a가 2인 경우에는 b번째 수부터 c번째 수의 합을 구하여 출력하면 된다.
입력으로 주어지는 모든 수는 -263보다 크거나 같고, 263-1보다 작거나 같은 정수이다.
출력
첫째 줄부터 K줄에 걸쳐 구한 구간의 합을 출력한다. 단, 정답은 -263보다 크거나 같고, 263-1보다 작거나 같은 정수이다.
풀이 방법
Lazy propagation 학습 및 적용해보았다 Lazy propagation 처음 이해하는데 좀 오래 걸리니 간단히 설명하자면 구간을 업데이트 할 때는 특정 구간을 나타내는 특정 노드가 3가지 변화 중 한가지가 있을 수 있다.
- 변화없음
- 일부 변화
- 전부 변화 2번은 이전 세그먼트트리와 동일하게 업데이트 하면 되는데 3번은 특별하게 처리해야한다. lazy에 저장된 값과 구간의 개수만큼 곱해 더해주고 lazy값을 자식에게 넘겨주는 과정이 필요하다. 그래서 변화하는 것을 lazy propagation으로 위에서부터 차례차례 더할 값을 지연시켜 자식에게 전달하며 더하는 것이다.
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
129
130
131
132
133
134
135
136
137
138
139
140
141
import java.io.*;
import java.util.*;
public class BOJ_10999_구간합구하기2 {
static BufferedReader br;
static BufferedWriter bw;
static StringTokenizer st;
static int N, M, K;
static long[] tree, lazy, num;
public static void main(String[] args) throws IOException {
// br = new BufferedReader(new InputStreamReader(System.in));
br = new BufferedReader(new InputStreamReader(new FileInputStream("input.txt")));
bw = new BufferedWriter(new OutputStreamWriter(System.out));
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
int treeHeight = (int) Math.ceil(Math.log(N) / Math.log(2));
int treeSize = 1 << (treeHeight + 1);
tree = new long[treeSize];
lazy = new long[treeSize];
num = new long[N+1];
for (int i = 1; i <= N; i++) {
num[i] = Long.parseLong(br.readLine());
}
// System.out.println(Arrays.toString(num));
init(1, N, 1);
for (int i = 0; i < M + K; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
long c = Long.parseLong(st.nextToken());
if (a == 1) { // 숫자 업데이트
long d = Long.parseLong(st.nextToken());
update_range(1, N, 1, b, (int) c, d);
}
else { // a==2 인 경우 - 합계산
bw.write(sum(1, N, 1, b, (int) c) + "\n");
}
}
bw.flush();
bw.close();
br.close();
}
/*
* 세그먼트 트리 초기화
* node : 세그먼트 트리의 정점 번호
* start : 이 정점이 관리하는 연속 구간의 왼쪽 끝
* end : 이 정점이 관리하는 연속 구간의 오른쪽 끝
*
*/
private static long init(int start, int end, int node) { // 최솟값 트리
if (start == end) return tree[node] = num[start];
int mid = (start + end) / 2;
return tree[node] = init(start, mid, node*2) + init(mid + 1, end, node*2 + 1);
}
/**
* Lazy propagation을 통해 현재 노드의 지연 값을 처리
* 노드의 지연 값(lazy[node])이 0이 아니면, 이 값을 현재 노드에 적용하고 자식 노드에 전달
*
* @param start
* @param end
* @param node
*/
private static void update_lazy(int start, int end, int node) {
if (lazy[node] != 0) {
tree[node] += (end - start + 1) * lazy[node];
if (start != end) {
lazy[node*2] += lazy[node];
lazy[node*2+1] += lazy[node];
}
lazy[node] = 0;
}
}
/*
* 세그먼트 트리 갱신
* node : 세그먼트 트리의 정점 번호
* start : 이 정점이 관리하는 연속 구간의 왼쪽 끝
* end : 이 정점이 관리하는 연속 구간의 오른쪽 끝
* from ~ to : 업데이트할 구간
* diff : 새로 더할 차이값
*
*/
private static void update_range(int start, int end, int node, int from, int to, long diff) {
update_lazy(start, end, node);
if (to < start || end < from) return;
if (from <= start && end <= to) {
tree[node] += (end - start + 1) * diff;
if (start != end) {
lazy[node*2] += diff;
lazy[node*2+1] += diff;
}
return;
}
int mid = (start + end) / 2;
update_range(start, mid, node*2, from, to, diff);
update_range(mid+1, end, node*2+1, from, to, diff);
tree[node] = tree[node*2] + tree[node*2+1];
}
// from ~ to 구간합
private static long sum(int start, int end, int node, int from, int to) {
// 현재 노드의 lazy 값을 처리한 후에 업데이트 적용
update_lazy(start, end, node);
// 덧셈 항등원 사용
if (to < start || end < from) return 0;
if (from <= start && end <= to) return tree[node];
int mid = (start + end) / 2;
return sum(start, mid, node * 2, from, to) + sum(mid + 1, end, node * 2 + 1, from, to);
}
}
참고자료
RANGE OPERATIONS: LAZY PROPAGATION Lazy Propagation in Segment Tree Do we actually need lazy propagation on segment trees? Lazy propagation in segment tree?