dustn9401   2년 전

update 함수를 조금 개선해야 할 것같은데.. 방법이 떠오르지를 않네요 ㅠㅠ


힌트 한번만 주시면 감사하겠습니다..

lyzqm   2년 전

하나의 index를 update하는데는 O(logN)이 걸립니다.
최악의 경우 구간 [1,N]을 update하는데 O(N*logN)이 되겠죠..

이러면 query가 M번 들어올 수 있으니 O(M*N*logN)이 되어서 시간초과가 발생합니다.
세그먼트 트리를 유지한채 lazy propagation라는 기법을 이용하면 해결할 수 있습니다.

dustn9401   2년 전

감사합니다... 참 벼라별게 다 있네요

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