개발일지

개념 Segment Tree에서 구간의 Update를 빠르게 처리하기 위한 방법이다. Segment Tree에서 Update의 시간 복잡도는 O(logN)이기 때문에 구간의 길이가 L인 Update의 시간 복잡도는 O(LlogN)이기 때문에 쿼리의 수가 많은 경우 시간초과를 받을 수 있다. Lazy Segment Tree는 Update를 필요한 시기에 Update하도록 미루면서 Range Update를 O(logN)으로 수행할 수 있다. 작동원리 구간을 Update할 경우 Segment Tree에서 참조하는 Node만 Update를 진행하고, 자식 노드의 Update는 Lazy Tree에 기록하여 Update를 미룬다. 시간 복잡도 init : O(NlogN) update : O(logN) update_..