[ 자료구조 ] 느리게 갱신되는 세그먼트 트리 (Lazy Propagation)

https://rudalsd.tistory.com/51

[ 자료구조 ] 세그먼트 트리 (Segment Tree)

1. 느리게 갱신되는 세그먼트 트리 (Lazy Propagation)

 

Lazy Propagation에서는 각 노드마다 lazy라는 값을 둡다. Lazy Propagation이라는 이름에서 알 수 있듯, 이 자료구조에서는 모든 값을 그때그때 갱신하지 않습니다. 굳이 갱신할 필요가 없는 노드에 대해서 lazy라는 값을 조정해 나중에 이 노드를 방문할 일이 생길 때까지는 갱신을 미루어 시간적 효율을 올리는 것입니다.

 

2. Lazy Propagation 만들기

 

Lazy Propagation을 만드는 방식은 일반적인 세그먼트 트리를 만드는 방식과 똑같습니다.

 

3. Lazy Propagation Update

 

Lazy Propagation에서 값을 수정하는 방법은 다음과 같습니다.

 

Update : 2 - 4 (+10)

Update : 2 - 4 (+10)

Update : 2 - 4 (+10)

Update : 2 - 4 (+10)

Update : 2 - 4 (+10)

Update : 2 - 4 (+10)

이렇게 2-4 구간에 대한 Update는 끝납니다. 일반적인 세그먼트 트리였다면 값이 갱신되는 리프 노드까지 내려갔다가 올라와야 하므로 더 오래 걸리지만 Lazy Propagation을 사용한다면 불필요한 방문을 줄여 훨씬 더 빠르게 갱신이 가능합니다.

 

이후 lazy값이 있는 노드에 방문한다면 노드에 그 값을 적용시키고 아래 노드에 물려줍니다.

 

4. Lazy Propagation 구간합 구하기

 

일반적인 세그먼트 트리와 구간합을 구하는 방식은 동일합니다. 하지만 해당 노드에 lazy값이 있다면 적용시킨 후 값을 더해주면 됩니다.