[질문] 피린이 세그먼트 트리 크기 질문

[익명(175.196)]

세그먼트 트리 크기 잡을 때 정석으로는

배열의 크기가 N이라 했을 때

트리 높이는 ceil(log2(N)) 이 되고

전체 크기를 1 << (트리 높이 + 1) 해주는 건 이해가 가는데

왜 이 크기가 N * 4 보다 작다는 게 보장됨?

[익명(27.35)]

2의 등비수열 합 공식 생각해바

[익명(175.196)]

2^N - 1 이 됨

[익명(27.35)]

웅 그럼 대충 2^(log N + c) 이 되니까 지수부 로그랑 밑 바꿔주면 N ~ 2N이 되겠징

[익명(175.196)]

+ c는 뭐야?

[익명(175.196)]

좀 더 자세히 설명 가능..? 형님

[익명(27.35)]

정확히는 log N의 ceil이니까 N이 2^k + 1 꼴이면 낭비되는 공간이 2배 (2N) 정도 더 생기겠지 근데 트리에서 리프 노드가 아닌 노드들의 개수가 2^(ceil(log N)) - 1이니까 여기서도 대략 2N 그래서 총합 최대 4N까지 나올 수 잇다..?

[익명(175.196)]

아 먼 말인지 조금 감 잡은 거 같은데

[자바땔감(coderhs)]

완전 이진트리 살펴보면 worst case가 가장 밑에 있는 리프 노드 절반 + 1개 차지하는 거잖아. 총 꼭지점 갯수는 (리프 노드 수 절반)*4 - 1이고

[자바땔감(coderhs)]

그래서 N에 비해 제일 작아질 때가 2*N-1(리프 노드 꽉 채우는 경우), 제일 커질 때가 4*N-5(리프 노드 절반 + 1개 채우는 경우) 라고 생각하고 4*N으로 대충 하더라.

[익명(175.196)]

아 진짜 친절하게 설명해준 거 같은데 이해가 안가네... 일단 ㄳㄳ

[캐티(tae826)]

리프노드를 N보다 큰 가장 가까운 2^n = m개로 설정해놓으면 총 노드수 = 2m-1 이고 m < 2n. 따라서 총 노드 수 < 4n

[자바땔감(coderhs)]

님 예전에 이거 모르고 3n으로 했다고 하지 않았음? 근데 그러기엔 너무 고인물인데

[익명(175.196)]

뭔 말이죠...;

[익명(39.121)]

ceil(x) < x+1이니까 트리 높이인 ceil(log2(N)) < log2(N)+1이라 2^(트리 높이 + 1) < 2^(log2(N)+2) = N*4