[일반] 세그먼트 트리 이해한 거 맞는지 확인 부탁 jpg

[익명(59.14)]

한가지 이해가 안가는 점이 있다면
최악의 경우가 왜 리프노드가 절반 + 1 이라는건지 모르겠음.

리프노드 1개가 ㄹㅇ 최악의 상황 아님?

[자바땔감(coderhs)]

1은 2K -1에 포함됨.. 1이 루트라는거 보여주려고 저렇게 그렸어.. ㅜㅜ 0은 트리 바깥에 있고.. 근데 뭐 대충 이해했으면 그러려니 하셈

[자바땔감(coderhs)]

그리고 리프노드는 무조건 반 이상 차야됨 안그러면 높이가 낮아지잖아

[익명(175.196)]

2K - 1에 1이 포함된다고? 아 그러네. 2K라는 게 결국 2의 배수인데 맨 위층 레벨은 루트 노드 하나밖에 없으니 -1 한 거구나.

[익명(175.196)]

엥 그림 그리니까 절반 이하로 찰 수 있는데?

[자바땔감(coderhs)]

그렇게 차면 높이가 올라간다고............

[익명(175.196)]

왜 높이가 올라가지 ㅠㅠ 어렵네

[자바땔감(coderhs)]

반도 안 차면 그 윗층에 채우면 되잖아 윗층 크기가 딱 절반이니까..

[익명(175.196)]

그 위층은 K개가 있는데?

[자바땔감(coderhs)]

반도 안 찼다 -> K개 이하다 -> 윗층에 채울 수 있다.

[ㅁ(119.202)]

어짜피 동작이 sigma(logn)인데 최고 최악을 따져서 뭐함

[자바땔감(coderhs)]

질문이 자료 갯수 N개 받았을 때 세그먼트 트리 크기를 4N으로 잡아도 되느냐였음

[익명(175.196)]

궁금하자너 왜 n * 4면 세그먼트 트리 전범위를 할당할 수 있는지

[ㅁ(119.202)]

N개를 저장하고 싶으면 N<=2^k인 최소의 2^k를 찾아야 하고 이때 사용공간은 2^k * 2 - 1개임. 2^k가 최소기 때문에 2^(k-1) < N <= 2^k가 성립하고, 따라서 사용공간 = 2^k * 2 -1 = 2^(k-1) * 4 - 1 < 4N-1

[익명(175.196)]

헐 그러네 ㅋㅋㅋ ㄳ ㄳ

[익명(118.235)]

그냥 리프노드를 주어진 배열 크기 이상이면서 가장 작은 2의 거듭제곱이라 생각하면 계산이 쉬움