Approach 단순히 세그먼트 트리로 구간에 대한 정보를 모두 처리하게 되면, 업데이트마다 MlgN만큼이 필요하게 된다. (단, M은 b ~ c 사이의 개수) 최악의 경우 NlgN이 필요하다. 따라서 단순히 세그먼트 트리로 이 문제를 해결할 경우 O(NKlgN) = 1000000 * 10000 * log10000이므로 무조건 시간 초과를 받게 된다. 위와 같은 상황에서 사용할 수 있는 자료구조가 Lazy propagation이다. 해당하는 자료는 다음을 참고하도록 하자. https://m.blog.naver.com/kdr06006/221818523719 세그먼트 트리 with Lazy Propagation 안녕하세요. 오늘은 lazy propagation에 대해 공부해보겠습니다. 세그먼트 트리에 laz..
[백준 10999번] [Lazy propagation] 구간 합 구하기 2
Approach 단순히 세그먼트 트리로 구간에 대한 정보를 모두 처리하게 되면, 업데이트마다 MlgN만큼이 필요하게 된다. (단, M은 b ~ c 사이의 개수) 최악의 경우 NlgN이 필요하다. 따라서 단순히 세그먼트 트리로 이 문제를 해결할 경우 O(NKlgN) = 1000000 * 10000 * log10000이므로 무조건 시간 초과를 받게 된다. 위와 같은 상황에서 사용할 수 있는 자료구조가 Lazy propagation이다. 해당하는 자료는 다음을 참고하도록 하자. https://m.blog.naver.com/kdr06006/221818523719 세그먼트 트리 with Lazy Propagation 안녕하세요. 오늘은 lazy propagation에 대해 공부해보겠습니다. 세그먼트 트리에 laz..
2022.03.09