2820번 - 자동차 공장
lazy 조회에서 균형된 트리일경우 lgN이고, 편향되있을경우 최악의 경우 O(N)이게 되잖아요
어쨋든 부모노드에서 lazy값이 있는지는 모두 조회해봐야 하니깐요
그럼 이문제에서는 lazy사용하게 되면 O(M*N) 이고,
최악의 상황인 각각 500,000 일떄, 시간초과가 무조건 날수밖에 없을것같은데
다른식으로 접근해야하는 걸까요?
세그먼트 트리는 균형잡힌 트리라서 쿼리, 업데이트가 logN입니다.
Lazy Propagation 이 아니어도 이 문제는 풀 수 있습니다.
세그먼트 트리를 Top-Down으로 쿼리하는 것이 아닌, Bottom-Up으로 쿼리하는 방향으로 접근하시면 Lazy Propagation 없이 푸실 수 있습니다.
댓글을 작성하려면 로그인해야 합니다.
cottage123 3년 전
lazy 조회에서 균형된 트리일경우 lgN이고, 편향되있을경우 최악의 경우 O(N)이게 되잖아요
어쨋든 부모노드에서 lazy값이 있는지는 모두 조회해봐야 하니깐요
그럼 이문제에서는 lazy사용하게 되면 O(M*N) 이고,
최악의 상황인 각각 500,000 일떄, 시간초과가 무조건 날수밖에 없을것같은데
다른식으로 접근해야하는 걸까요?