cottage123   3년 전

lazy 조회에서 균형된 트리일경우 lgN이고, 편향되있을경우 최악의 경우 O(N)이게 되잖아요

어쨋든 부모노드에서 lazy값이 있는지는 모두 조회해봐야 하니깐요


그럼 이문제에서는 lazy사용하게 되면 O(M*N) 이고,

최악의 상황인 각각 500,000 일떄, 시간초과가 무조건 날수밖에 없을것같은데

다른식으로 접근해야하는 걸까요?

Green55   3년 전

세그먼트 트리는 균형잡힌 트리라서 쿼리, 업데이트가 logN입니다.

pl0892029   3년 전

Lazy Propagation 이 아니어도 이 문제는 풀 수 있습니다.

세그먼트 트리를 Top-Down으로 쿼리하는 것이 아닌, Bottom-Up으로 쿼리하는 방향으로 접근하시면 Lazy Propagation 없이 푸실 수 있습니다.

댓글을 작성하려면 로그인해야 합니다.