Lazy Propagation In Segment Tree

일부 updates를 미루면서, 구간 updates를 최적화 시키는 알고리즘

Problem

위의 그림은, 구간의 합을 저장하는 Segment Tree이다. 이를 통해, 하나의 값을 갱신할 때, 구간의 합도 O(logN)이라는 빠른 시간 안에 update 할 수 있다.

그러나, 값 하나를 update 하는 게 아니라, 특정 range의 모든 값들을 update해야 한다면 어떨까? range가 M이라고 할 때 O(MlogN)이 걸린다.

물론, 기본 Segment Tree도 빠르지만, 이런 상황이 계속 주어지면 많은 시간을 요구하게 된다.

Solution

이를 개선하기 위한 알고리즘이, Lazy Propagation이다.
이름 그대로, updates를 연기한다. 예를 들어, 위와 같은 상황에서 arr[3]부터 arr[5]까지의 값들에 10을 더한다고 가정해 보자. ST에서 27이 저장된 node에 10*3 을 더해주고, 나머지 children nodes는 필요시 다음에 update 한다.

아래는 pseudocode이다.

/* val[l...r]을 updates 해야할 때,
 * ST를 update하는 함수
 * */
updateRange( l, r ):
  1) 현재 node에 pending updates가 있다면,
      a) update를 진행한다.
  2) 현재 node가 update 대상 구간이라면, 
      a) update: 현재 node를 update한다.
      b) postpone: 차후에 진행할 lazy 값을 저장하여, children nodes의 update를 미룬다.
  3) 현재 node가 update 대상 구간을 일부 포함,
      a) recursive call을 통해 좌우 구간을 update

시간 복잡도는 O(logN)이다.

Data Structure

• ST[size], Segment Tree 저장용
• lazy[size], pending updates 저장용. ST[idx]에 대한 값을 lazy[idx]에 저장.

(size나 다른 자세한 내용은, Segment Tree 링크를 참조.)