문제 풀이 날짜: 2023.08.02
포스트 작성일: 2023.10.12
* 학습 목적으로 작성하는 글입니다. 풀이가 정석적이지 못할 수도 있습니다.
문제 출처
백준 온라인 저지 2042번 : 구간 합 구하기 (골드1)
키워드
세그먼트 트리, 부분 합
풀이 접근법
- 단순 배열로 풀이하려고 하면 시간 초과가 발생한다. 배열은 선형 탐색을 진행하기 때문에 O(N) 시간을 소모하기 때문이다.
- 따라서 더욱 빠른 자료 구조인 세그먼트 트리를 이용하여 풀이한다.
- 세그먼트 트리란, 트리의 특징을 이용하여 구간 합의 계산이나 값의 수정을 O(logN) 시간만에 해결할 수 있는 자료구조이다.
- 트리의 특성 상 값 초기화나 검색은 재귀로 구현한다.
- 트리의 리프노드에 초기값들을 저장하고, 위로 올라갈 수록 더 큰 부분합이 저장되는 형태이다.
코드
import java.io.*;
public class Main {
private static long[] tree;
private static long[] arr;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] temp = br.readLine().split(" ");
int N = Integer.parseInt(temp[0]);
int M = Integer.parseInt(temp[1]);
int K = Integer.parseInt(temp[2]);
arr = new long[N + 1]; //0은 사용하지 않음
for(int i = 1; i <= N; i++) {
arr[i] = Long.parseLong(br.readLine());
}
tree = new long[4 * N];
init(1, N, 1); //1부터 N까지 부분합을 초기화한다.
StringBuilder sb = new StringBuilder();
for(int i = 0; i < M + K; i++) {
temp = br.readLine().split(" ");
int a = Integer.parseInt(temp[0]);
int b = Integer.parseInt(temp[1]);
long c = Long.parseLong(temp[2]);
long diff = 0;
if(a == 1) {
diff = c - arr[b];
arr[b] = c;
update(1, N, 1, b, diff);
} else if(a == 2) {
long result = sum(1, N, 1, b, (int)c); //1부터 N번 노드까지 탐색, b~c 구간합 계산
sb.append(result).append("\n");
}
}
System.out.println(sb);
}
private static long init(int start, int end, int node) {
if(start == end) {
return tree[node] = arr[start]; //노드값으로 시작점을 달아준다.
}
int mid = (start + end) / 2; //이분 탐색
//두 자식 노드의 부분합을 저장한다.
return tree[node]
= init(start, mid, node * 2) + init(mid + 1, end, node * 2 + 1);
}
private static long sum(int start, int end, int node, int left, int right) {
if(left > end || right < start) //탐색 범위 밖에 있다면
return 0;
if(left <= start && end <= right) //탐색 범위 안에 있다면
return tree[node]; //노드값을 반환
//그렇지 않으면 두 부분으로 나누어 다시 탐색
int mid = (start + end) / 2;
return sum(start, mid, node * 2, left, right)
+ sum(mid + 1, end, node * 2 + 1, left, right);
}
private static void update(int start, int end, int node, int index, long diff) {
if(index < start || index > end) //범위 밖에 있다면 리턴
return;
//범위 안에 있으면 내려가며 다른 원소도 갱신
tree[node] += diff;
if(start == end)
return;
int mid = (start + end) / 2;
update(start, mid, node * 2, index, diff);
update(mid + 1, end, node * 2 + 1, index, diff);
}
}
참고한 링크
https://steady-coding.tistory.com/124
'Study > Problem Solving' 카테고리의 다른 글
| [백준 / Java] 17144번: 미세먼지 안녕! (골드4) (0) | 2023.10.16 |
|---|---|
| [SWEA / Java] 5656번: [모의 SW 역량테스트] 벽돌 깨기 (0) | 2023.10.16 |
| [SWEA / Java] 5658번: [모의 SW 역량테스트] 보물상자 비밀번호 (1) | 2023.10.05 |
| [백준 / Java] 4485번: 녹색 옷 입은 애가 젤다지? (골드4) (1) | 2023.10.05 |
| [백준 / Java] 2458번: 키 순서 (골드4) (0) | 2023.10.04 |