smu201111192   4년 전

요문제를 세그먼트 트리를 이용해서 풀어봤는데요.

세그먼트 만들 때 데이터크기에 4배 정도로 트리 공간을 잡으면 되는걸로 알고있습니다.

근데 요문제는 4배~6배로 잡으면 틀리고 7배이상으로 잡아줘야 맞습니다. 

왜그럴까요? ㅠ


yukariko   4년 전

간단하게 아래 코드로 테스트하니 pos의 값이 최대 4 N 근처가 나오네요

거기에 코드의 pos * 2를 인덱스로 접근하니 8N의 범위까지 가게 될것 같습니다.

yukariko   4년 전

코드를 이렇게 하니 4N으로도 풀리긴하네요


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