[Algorithm] Segment tree with Lazy propagation (BOJ 10999)

• segment tree with lazy propagation algorithm의 필요성 segment tree는 구간에 대한 query를 O(logN)에 수행할 수 있도록 한다. 한 index에 대한 update를 수행할 경우에 update의 time complexity는 역시 recursive call에 의해서 O(logN)에 수행된다. 만약 한 index가 아니라 구간 [L, R]에 대한 update를 수행할 경우 [L, R]에 속한 모든 index에 대하여 update를 해 주어야 하므로 O((R-L+1)logN), 일반적으로 쓰면 O(NlogN)의 긴 수행 시간이 필요하게 된다. 이를 해결하기 위해서는 일종의 optimization이 필요한데, 이것이 바로 lazy propagation이다...