티스토리 뷰
Segment Tree with Lazy Propagation
gaelim 2019. 3. 10. 15:19세그먼트 트리 with Lazy Propagation
Introduction
만약 문제를 풀 때 구간 질의와 관련된 문제에서 naive한 방법 또는 잘 알려진 prefix 계열의 접근으로도 풀 수 없는 것이 있다면, 한 번쯤 생각해볼 방법은 세그먼트 트리이다.
세그먼트 트리는 구간에 대해 분할 해놓은 정보들을 담고 있는 트리이다.
루트노드는 [0 ... n-1] 구간에 대한 특정 연산 결과가 담겨있고. 그 자식 노드는 [0 ... (n-1)/2], [(n-1)/2+1 ... n-1] 구간에 대한 특정 연산 결과가 담겨있다. 이는 초기화 단계 init 에서 수행된다.
이러한 트리는 분할정복을 따르며, 재귀적으로 파고 들어가 자식노드의 결과값을 부모노드가 받고 또 그 결과를 재사용하기 때문에 납득할 만한 초기화 수행복잡도를 가질 수 있다. 트리의 높이는 최대 h = ceiling(log n) 이다.
세그먼트 트리를 생성하는 것은 초기화 단계라고 하며, 이는 세그먼트 트리를 이용해 문제를 풀기위한 기본단계이다.
세그먼트 트리에 주로 하는 쿼리는 두 가지로 정의 될 수 있다.
1 구간에 대한 특정 연산 수행 후 결과물 출력 : 이는 구간을 저장하고 있는 노드들에 접근하기 때문에 최대 높이 log n 안에 가능하다. 여러 노드를 접근할 수 있으므로 앞에 상수가 붙는다.
2 단일 원소에 대한 수정 : 이 쿼리가 들어오면 그 원소를 포함하는 모든 구간 쿼리 정보 수정을 log n 수행복잡도에 해낼 수있다.
Lazy Propagation의 필요성
이 경우 naive 세그먼트 트리에서 2 와 같은 수행을 하였다고 하자. 그러면 수행복잡도는 (qr-ql+1) * log n 이다. 여기서 ql =query left, qr = query right.
그러면 백준 구간 합 구하기2 문제 조건에 따라 구간에 대한 수정 쿼리가 1e4 번 존재하고, 해당 수정 쿼리 모두가 모든 구간 [1 .. 1e6] 에 대해 걸쳐있다 하자.
[ 1 .. 1e6 ] 에 대한 구간 수정을 1회 수행하는데 수행복잡도는 (qr-ql+1) * log n = ( 1e6 ) * log 1e6 이다.
이런 쿼리가 1e4 번 존재하니 수행복잡도는 1e10 * log 1e6 이며, 100억을 뛰어넘는다.
naive한 Segment Tree 접근법으로는 문제를 효율적으로 해결 할 수 없다.
Lazy Propagation은 다음을 시사한다. 구간에 대한 일괄 수정을 굳이 바로 할 필요가 있을까?
[ 1 .. 1e6 ] 구간에 대해 일괄적인 수정을 한다고 하자.
기본적인 세그먼트 트리를 이용한다면, 단일 원소 [1] 에 대한 구간 수정을 먼저할 수 있다. 세그먼트 트리의 루트 노드 에서부터 타고내려가 [1] 혼자만 있는 노드까지 모두 수정해줘야한다.
Lazy Propagation은 이 수정을 잠깐 미룬다는 것이다. 원래 쿼리로 돌아가 [ 1 .. 1e6 ] 구간을 일괄적으로 변경한다고 하자.
이 때 [1] 구간을 포함하는 모든 노드를 탐색하며 수정할 필요없이, [ 1 .. 1e6 ] 에 대한 일괄적 수정을 [ 1 .. 1e6 ] 구간을 표현하는 노드에 lazy 배열을 따로 두어 저장해 두는 것이다.
그리고 만약 다음 쿼리에 [ 1 ] 구간에 대한 쿼리가 온다면 그 때 노드들을 타고내려가며 lazy 배열에 저장된 정보들을 전파한다.
따라서, 해당 노드에 대한 물어보는 쿼리가 들어올 때 이전 업데이트 쿼리가 적용 됨을 알 수 있다. 혹은 문제 필요에 따라 이전 업데이트들을 적용해준다.
이 설명이 부족할 것이다.
백준님이 게시하신 블로그에서 더 자세한 구현방법을 살펴보고, 따라 작성하시면 도움이 될 것입니다.
https://www.acmicpc.net/blog/view/26
'Discrete mathmatics and Problem Solving > 11 트리' 카테고리의 다른 글
AVL tree (0) | 2018.10.28 |
---|---|
B+ trees (0) | 2018.10.27 |
Binary Search Tree, 이진 검색 트리 (0) | 2018.10.25 |
이진 힙과 힙정렬 binary heap && heap sort (0) | 2018.02.06 |
트라이 자료구조Trie datastruct (2) | 2018.01.12 |
- Total
- Today
- Yesterday
- 조합 코딩
- 자바스크립트 예제
- javascript
- Arena
- Propositional and Predicate Logic
- 대규모 시스템 설계 기초
- 시뮬레이션
- grafana cloud
- 그라파나
- 엄청난 인내심과 시뮬레이션을 위한 아레나 툴
- Trie
- 이산수학
- 백준
- Simulation
- 명제논리
- arena simulation
- 아레나 시뮬레이션
- Discrete Mathematics
- flutter
- 데이터 중심 애플리케이션 설계
- 로젠
- 아레나시뮬레이션
- 이산 수학
- 아레나
- beginning javascript
- 최단경로 알고리즘
- 가상 면접 사례로 배우는 대규모 시스템 설계 기초
- 자바스크립트
- paul wilton
- rosen
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |