정리/자료구조+알고리즘
세그먼트 트리(Segment Tree)
javaju
2021. 7. 1. 15:36
세그먼트 트리(Segment Tree)
- 특정 구간 내 연산에 대해서 빠르게 응답하기 위해 만들어진 자료구조
- 1,2,3,4,5라는 수들 중 2번째부터 5번째까지의 합을 구하고 싶다!
= 배열로 구간합을 저장하고 sum[5] - sum[1]으로 구할 수 있다. -> 시간 복잡도 : O(1)
- 만약 배열의 값이 바뀐다면?
= 바뀔때마다 구간합을 더해서 다시 저장해야한다. -> 시간 복잡도 : O(N^2)
- 세그먼트 트리를 사용했을 경우에는 시간 복잡도 O(NlogN)
- 세그먼트 트리 만들기
구현
- 트리 만들기
|
1
2
3
4
5
|
public static int init(int node_idx, int start, int end) {
if(start==end) return tree[node_idx] = arr[start]; //start == end인 경우 : leaf노드
// 자식노드를 더한다 (왼쪽 노드 + 오른쪽 노드) return tree[node_idx] = init(node_idx*2, start, (start+end)/2) +
init(node_idx*2+1, (start+end)/2+1, end); }
|
cs |
- 배열 값 변경 (구간합 수정)
|
1
2
3
4
5
6
7
8
9
10
|
public static void update(int node_idx, int start, int end, int idx, long diff) {
if(idx < start | idx> end) return;
tree[node_idx]+=diff;
if(start!=end) {
update(node_idx*2,start,(start+end)/2,idx,diff);
update(node_idx*2+1, (start+end)/2+1, end, idx, diff);
}
}
|
cs |
- 구간합 구하기
|
1
2
3
4
5
6
7
8
9
|
public static int sum(int node_idx, int start, int end, int L, int R) {
if(end<L || start>R) return 0;
if(L<=start && end<=R) return tree[node_idx];
return sum(node_idx*2, start, (start+end)/2,L,R) +
sum(node_idx*2+1, (start+end)/2+1, end, L,R); }
|
cs |
세그먼트 트리 관련 문제
2042번: 구간 합 구하기
첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄
www.acmicpc.net