dydsj0920   1년 전

어떻게 설정해 주는것이 좋을까요?

N이 100000개가 최대값인데

이것이 세그먼트 트리의 정점 개수라고 볼수는 없을거 같은데요..

배열의 크기 지정때문에 몇번이나 틀렸네요 ㅎㅎ


cheetose   1년 전

저 같은 경우에는 일단 2를 계속 곱해서 처음으로 N을 넘어가는 수를 찾아요. 여기서는 N이 10만이니까 131072이겠네요. 여기서 2를 한 번 더 곱해서, 즉 262144를 트리의 사이즈로 잡습니다.

dydsj0920   1년 전

그렇군요 감사합니다!

dydsj0920   1년 전

cheetose

근데 2를 계속 곱해서 처음으로 N을 넘어가는 수는 왜 찾으신거죠?

로그 지수가 2인 logN = 트리의 높이 H 필요한 정점의 개수는 2^(H+1) 이런식으로 구하신거 같은데 맞나요?

cheetose   1년 전

처음으로 N이 넘어가는 그 수가 세그먼트 트리의 리프노드의 개수라고 생각하시면 돼요.

그리고 리프노드가 2^N 개라면 리프노드가 아닌 노드의 개수가 2^N-1이어서 2를 한 번 더 곱하는 거고요

dydsj0920   1년 전

답변 감사합니다

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