kyaryunha   4년 전

예시 데이터로는 잘 되는데, 

제출하니 시간초과가 납니다..!


혹시 왜 시간초과가 나는지 알려주실 분 계실까요?

chogahui05   4년 전

update 함수의 복잡도는 O(logn)이 되게 짜셨을 테고..

최악의 경우에 한 Query당 O(nlogn)이 되게 짜셨네요. 그러니 시간 초과가 나실수밖에 없네요.

kyaryunha   4년 전

앗ㅅ... 그럼 혹시 펜윅트리 시간복잡도 어떻게 하면 더 줄일 수 있나요??

chogahui05   4년 전

레이지 프로퍼레이션이였나? 그 알고리즘 한 번 배워보세요.

kyaryunha   4년 전

헉ㄱ..  그렇게 짰다고 생각 했는데.. 그럼에도 시간초과 난거거든요 ㅠㅠ..... diff가 그 변화량을 의미해요..!! 


chogahui05   4년 전

에이.. ky님이 짜신 코드는 레이지 같지만 레이지가 아니에요.

업데이트를 하실 때 b부터 c까지 일일히 하시잖아요. 레이지는

업데이트를 추후에 하면 좋지 않을까? 라는 개념입니다. 아주 간단..하게 말하면.

kyaryunha   4년 전

헉ㄱ 그렇군요..! 자세히 다시 찾아보고 코드 수정해야 겠어요..!! 

조언 감사합니다~!~!!~!!!

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