Segment Tree with Lazy Propagation

Discrete mathmatics and Problem Solving/11 트리

gaelim 2019. 3. 10. 15:19

세그먼트 트리 with Lazy Propagation

만약 문제를 풀 때 구간 질의와 관련된 문제에서 naive한 방법 또는 잘 알려진 prefix 계열의 접근으로도 풀 수 없는 것이 있다면, 한 번쯤 생각해볼 방법은 세그먼트 트리이다.

세그먼트 트리는 구간에 대해 분할 해놓은 정보들을 담고 있는 트리이다.

루트노드는 [0 ... n-1] 구간에 대한 특정 연산 결과가 담겨있고. 그 자식 노드는 [0 ... (n-1)/2], [(n-1)/2+1 ... n-1] 구간에 대한 특정 연산 결과가 담겨있다. 이는 초기화 단계 init 에서 수행된다.

이러한 트리는 분할정복을 따르며, 재귀적으로 파고 들어가 자식노드의 결과값을 부모노드가 받고 또 그 결과를 재사용하기 때문에 납득할 만한 초기화 수행복잡도를 가질 수 있다. 트리의 높이는 최대 h = ceiling(log n) 이다.

세그먼트 트리를 생성하는 것은 초기화 단계라고 하며, 이는 세그먼트 트리를 이용해 문제를 풀기위한 기본단계이다.

세그먼트 트리에 주로 하는 쿼리는 두 가지로 정의 될 수 있다.

Lazy Propagation은 표현 그대로 Lazy하다. 왜 Lazy가 필요한지 필요성에 대해서 이야기 해보자.

먼저 구간에 대한 새로운 쿼리를 정의하자.

3 구간 원소에 대한 수정 : 이 쿼리가 들어오면 그 구간에 대해 일괄적인 수정을 수행한다.

이 경우 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 배열에 저장된 정보들을 전파한다.

따라서, 해당 노드에 대한 물어보는 쿼리가 들어올 때 이전 업데이트 쿼리가 적용 됨을 알 수 있다. 혹은 문제 필요에 따라 이전 업데이트들을 적용해준다.

이 설명이 부족할 것이다.

백준님이 게시하신 블로그에서 더 자세한 구현방법을 살펴보고, 따라 작성하시면 도움이 될 것입니다.