#11 Segment Tree With Lazy Propagation

segment tree는 구간 쿼리 + 원소 업데이트 쿼리 혹은 구간 업데이트 쿼리 + 원소 쿼리 등을 

각각 O(log N)에 처리할 수 있는 자료구조이다.

 

Lazy Propagation이란 테크닉을 이용하면, 구간 업데이트+구간 쿼리를 각각 O(log N)에 처리할 수 있다.

Lazy Propagation은 보통 top down방식의 segment tree를 이용한다.

 

Lazy Propagation이라는 단어는 직역하면 느리게 전파한다 라는 뜻을 가지고있다.

핵심 아이디어는 업데이트를 굳이 지금 할 필요가 없으면 나중에 한다는 아이디어에서 시작한다.

위의 트리는 구간을 나타내는 segment tree입니다. [1, 11]

여기서 구간 [3, 6]을 update해보자

파란색으로 칠해진 노드들을 update해야 한다.

이 모든 노드들을 실제로 전부 update하기엔 수가 너무 많다. 최악의 경우엔 O(N) 이다.

여기서 Lazy Propagation 방법이 사용되는데 실제로 구간의 update를 지금은 빨간색 부분만 하고

나중에 필요할 때, 파란색 부분까지 update를 하자는 것이다. 

몇몇 구간은 update를 하지 않고 미루기 때문에 O(log N)으로 효율적으로 구할 수 있다.

 

이 상태에서 3~4 까지 합을 구하는 쿼리가 들어오면?

노란색 부분의 합을 구해야 한다.

그런데 이 그림을 보면 노란색 부분은 update가 되었어야 하는데, update가 안된 상태이다.

따라서 전파해주는 작업이 필요하다 (propagation)

그럼 상태가 이렇게 되는데 합 쿼리에서 최대 O(log N)개의 구간 만을 살펴보므로, propagate 작업을

실시하는데도 O(log n)의 시간복잡도가 필요하다.

 

예시문제

백준 10999 (구간 합 구하기 2)

예시문제

백준 12895 (화려한 마을) c++