devbelly

문제 www.acmicpc.net/problem/10999 알고리즘 lazy propagation 풀이 구간 갱신, 구간 쿼리를 요구하는 문제입니다. 일반적인 점 갱신, 구간 쿼리를 이용하는 세그먼트 트리를 활용한다면 구간 갱신을 처리할 때, 구간의 길이에 비례한 시간복잡도를 요구합니다. 하지만 lazy propagation을 활용하면 구간 갱신또한 $O(logN)$에 훌륭하게 처리가능합니다. 자세한 설명은 다른 좋은 글들이 많으니 참고 바랍니다. 구현 포인트만 짚고 마치겠습니다. 1. $lazy$를 업데이트 하는 것은 쿼리와 업데이트 둘 다 해당이 된다. 2. 조상노드에서 자식노드로 재귀적으로 $lazy$를 업데이트 해야한다. 3. 자식노드의 $lazy$는 조상노드를 고려해야한다. 4. 세그먼트 트리를..