[백준] 10999구간 합 구하기 2
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
2020-12-21
|
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
|
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main10999 {
public static int N, M, K;
public static long arr[], tree[], lazy[];
public static long init(int node, int start, int end) {
if(start == end) return tree[node] = arr[start];
int mid = (start + end) / 2;
return tree[node] = init(node*2, start, mid) + init(node*2+1, mid+1, end);
}
public static void updateLazy(int node, int start, int end) {
if(lazy[node] != 0) { //lazy값이 0이 아닌 경우
tree[node] += (end-start+1)*lazy[node]; //해당하는 노드가 담당하는 노드의 총 갯수 * 해당 노드의 lazy 값
//leaf노드가 아닌 경우
if(start != end) {
lazy[node*2] += lazy[node]; //자식들에게 lazy 값을 물려준다
lazy[node*2+1] += lazy[node];
}
lazy[node] = 0; // 물려준 후 해당 노드 lazy는 초기화
}
}
public static void updateRange(int node, int start, int end, int left, int right, long diff) {
updateLazy(node, start, end); //해당 노드에 lazy가 있다면 업데이트
if(left > end || right < start) return;
if(left <= start && end <= right) { //범위에 해당할때
tree[node] += (end-start+1)*diff; //해당하는 노드가 담당하는 노드의 총 갯수 * 더하거나 빼야할 값
if(start != end) { // leaf노드가 아닌 경우
lazy[node*2] += diff; // 자식들에게 lazy 값을 물려준다
lazy[node*2+1] += diff;
}
return;
}
int mid = (start + end) / 2;
updateRange(node*2, start, mid, left, right, diff);
updateRange(node*2+1, mid+1, end, left, right, diff);
tree[node] = tree[node*2] + tree[node*2+1];
}
public static long sum(int node, int start, int end, int left, int right) {
//남은 lazy들을 update시켜준다
updateLazy(node, start, end); //updateLazy
if(left > end || right < start) return 0;
if(left <= start && right >= end) return tree[node]; // 범위안에 있는 경우만
int mid = (start + end) / 2;
return sum(node*2, start, mid, left, right) + sum(node*2+1, mid+1, end, left, right);
}
public static void main(String[] args) throws Exception {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(bf.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
arr = new long[N+1];
tree = new long[N*4];
lazy = new long[N*4]; //update를 미루는 배열
for(int i = 1; i <= N; i++) {
st = new StringTokenizer(bf.readLine().trim());
arr[i] = Long.parseLong(st.nextToken());
}
init(1, 1, N);
for(int i = 0; i < M+K; i++) {
st = new StringTokenizer(bf.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
//기존 세그먼트 트리에서 하냐의 값을 변경할 때에는 O(logN)의 시간이 걸렸다.
//이 알고리즘을 활용하여 구간의 값들을 변경하면 (c-b+1)만큼 변경해야하므로 O(NlogN)만큼 걸리게 되고 TLE가 된다.
//이것을 해결하기 위해 Lazy Propagation을 활용해야한다. O(logN)^2이 걸린다.
if(a == 1) {
long d = Long.parseLong(st.nextToken());
updateRange(1, 1, N, b, c, d); // b번째 수부터 c번째 수에 d를 더한다.
} else {
System.out.println(sum(1, 1, N, b, c)); //b번재 수부터 c번째 수까지 합을 구한다.
}
}
}
}
|
cs |
세그먼트 트리 나중에 업데이트 해야지!
배열 A가 있고, 여기서 다음과 같은 두 연산을 수행해야하는 문제가 있습니다. 10999번 문제: 구간 합 구하기 2 구간 l, r (l ≤ r)이 주어졌을 때, A[l] + A[l+1] + ... + A[r-1] + A[r]을 구해서 출력하기 i번째
www.acmicpc.net
Lazy Propagation에 대한 지식이 없어서, 위의 링크와 여러 블로그를 참고해서 개념을 익히고 문제를 풀었다.
2042번: 구간 합 구하기
첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄
www.acmicpc.net
구간 합 구하기 (1) 같은 경우는 구간의 변경이 아니라 하나의 값에 대한 변경이어서 O(logN)의 시간으로도 TLE가 나지 않고 해결이 되었다. 하지만 구간 합 구하기 (2)같은 경우는 기존 세그먼트 트리 방식으로 풀면 TLE가 나는 문제이다. Lazy Propagation을 활용하여 특정 구간의 update를 나중에 해주어 TLE를 막을 수 있다.