jason9319   4년 전

parallel binary search를 공부하려고  boj 8217번을 공부하다가 궁금증이 생겼는데

문제에서 구간의 합을 처리하는 연산을 보통 다 bit를 이용해서 처리해주시더라구요

저는 lazy propagation를 이용한 segment tree로 처리를 했는데 TLE를 맞아서

이용한 자료구조만 다를 뿐인데 시간차이가 나길래 ㅜㅜ

lazy_propagation에서 업데이트나 쿼리를 처리하는 시간복잡도가 logN이 보장되는거 아닌가요?

물론 제가 잘못 구현하였을수도 있습니다..


jason9319   4년 전

답변해주신 @cubelover님 @zlzmsrhak님 감사합니다

byeongkeunahn   3년 전

Segment Tree with Lazy Propagation으로 3초 후반에서 4초 중반 정도로 통과 가능한 것 같습니다. BIT로는 1.5초 정도 나왔습니다

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