11658번 - 구간 합 구하기 3
쿼드트리도 시간복잡도가 쿼리, 업데이트 모두 O(logN) 로 알고있는데 시간초과가 뜨네요.
N <= 1024, M <= 100,000 이니까
O(1024*1024 *log(1024) + 100,000 * log(1024)) 가 아닌건가요?
https://stackoverflow.com/ques...
O(N)입니다.
@herdson
이진트리의 최악의 경우랑 같은 이야기인것 같은데, 위 경우에서는 완전이진트리가 보장되므로 관계없지 않나요?
댓글을 작성하려면 로그인해야 합니다.
dh0450 2년 전
쿼드트리도 시간복잡도가 쿼리, 업데이트 모두 O(logN) 로 알고있는데 시간초과가 뜨네요.
N <= 1024, M <= 100,000 이니까
O(1024*1024 *log(1024) + 100,000 * log(1024)) 가 아닌건가요?