aaadddggg   2년 전

원소의 갯수가 N이라 할 때

1. 세그먼트 트리의 높이 h = 올림(logN)로 구할 수 있고,

 2. 2^(h + 1) 로부터 세그먼트 트리의 노드 갯수를 구할 수 있다. by 백준님 블로그 설명(https://www.acmicpc.net/blog/v...)

n4.png

n3.png

제 의문은 N이 2의 거듭제곱꼴을 만족하던 안하던 일반적인 경우에 단순히 2 * N - 1로 세그먼트 트리의 노드 갯수를 결정할 수 있으리라 생각되는데 실제로 2N - 1로 갯수를 정하니 런타임 오류가 발생하였습니다.

결국 백준님 블로그에 따르는 갯수 정하는 방식은 꽉찬 이진 트리 형식이 되게하는 방식으로 보이는데 왜 굳이 꽉 채워야하는지 납득이 가질 않습니다. 

다음 코드는 세그먼트 트리의 값을 초기화해주는 함수입니다. 이부분에서 큰 n에 대해 에러가 발생함을 확인하였습니다.

ntopia   2년 전

N=6 일 때 트리가 어떻게 생겼는지 한번 그려보세요

중간에 빈틈이 생기죠?

그래서 세그트리를 배열로 구현한 경우에는 index가 (위 소스에선 node 변수) 2*N-1 을 넘어갈 수 있게 돼요.

그래서 그런 상황에서의 귀찮은 예외처리를 피하고자 애초에 공간을 저렇게 넉넉하게 잡는 것이고요.

aaadddggg   2년 전

빈공간에도 node가 할당됨을 간과하였네요! 정말 감사합니다!!

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