728x90
1. 세그먼트 트리
주어진 데이터의 구간합과 데이터 업데이트를 빠르게 수행하기 위해 고안해낸 자료구조
2. 구간합
합배열(prefix sum)은 업데이트가 느림
- arr[1]를 update 한다면 ? sum[1]부터 sum[9]까지 모든 값을 update 해야함 ➔ 느림
- 데이터의 업데이트가 빈번하게 일어나게 되면 합배열 성능 측면에서 안좋음 ➔ 속도유지를 위해 세그먼트 트리 사용
2. 원리
1) 트리 초기화 하기
⓪ 샘플데이터 {5, 8, 4, 3, 7, 2, 1, 6}
① 리스트 길이
- 데이터의 개수(N) 이상이 되도록 트리 리스트를 만듬
- 2ᵏ≥ N을 만족하는 𝑘의 최솟값을 구한 후 2ᵏ * 2
- N=8이므로 2³ ≥ 8 ➔ 2³ * 2 = 16
② 시작 노드 : 2ᵏ ➔ 2³ = 8
③ 리프 노드에 원본 데이터 채우기
|
0
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
11
|
12 | 13 | 14 | 15 |
| 5 | 8 | 4 |
3
|
7
|
2
|
1
|
6
|
④ 리프 노드를 제외한 나머지 노드의 값 채우기: 2ᵏ 부터 1번쪽으로
- 구간합 A[N] = A[2N] + A[2N+1]
|
0
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
11
|
12 | 13 | 14 | 15 |
| 36 | 20 | 16 | 13 | 7 | 9 | 7 | 5 | 8 | 4 |
3
|
7
|
2
|
1
|
6
|
- 최대 A[N] = max( A[2N], A[2N+1])
|
0
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
11
|
12 | 13 | 14 | 15 |
| 8 | 8 | 7 | 8 | 4 | 7 | 6 | 5 | 8 | 4 |
3
|
7
|
2
|
1
|
6
|
- 최소 A[N] = min ( A[2N], A[2N+1])
|
0
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
11
|
12 | 13 | 14 | 15 |
| 1 | 3 | 1 | 5 | 3 | 2 | 1 | 5 | 8 | 4 |
3
|
7
|
2
|
1
|
6
|
2) 질의값 구하기
질의값 구하는 과정
- start_index % 2 == 1 일 때 해당 노드를 선택한다.
- end_index % 2 == 0 일 때 해당 노드를 선택한다.
- start_index depth 변경 : ( start_index + 1 )/2
- end_index depth 변경 : ( end_index + -1 )/2
- 1~4을 반복하다가 end_indx < start_index가 되면 종료
1~2에서 노드를 선택했다는 것
해당 노드의 부모가 나타내는 범위가 질의 범위를 넘어가기 떄문에 해당 노드를 질의값에 영향을 미치는 독립 노드로 선택하고,
해당 노드의 부모 노드는 대상 범위에서 제외한다는 뜻
예시
728x90