[일반] 세그먼트 트리 필요한 노드 갯수 정확히 어떻게 셈?

[울댕별(mypuppystarpoo)]

세그먼트트리 검색해보면 그냥 대~~충 리프노드 * 4 하면 적당하다느니 그런말만 해서 개빡치는데 정확히 필요한 노드 개수 공식이 어떠케됨? 수학 노베이스라서 혼자 못알아내겟음

- dc official App

[EN_SA(encludingsalt)]

2^ceil(log2 N)

[EN_SA(encludingsalt)]

바텀업 구현은 그냥 2N이라고 하던

[울댕별(mypuppystarpoo)]

리프 4개일때 총 노드 7개 아님?

[EN_SA(encludingsalt)]

맞네 잠시만

[울댕별(mypuppystarpoo)]

나도개화남

[EN_SA(encludingsalt)]

2^(ceil(log2(N))+1) - 1 + n - 2^floor(log2(N))? 딱맞춰보려니 화나네

[EN_SA(encludingsalt)]

으앙

[익명(211.246)]

보통 0번노드 비우기때문에 총 8개맞음

[울댕별(mypuppystarpoo)]

천재다

[익명(27.176)]

1 << ceil(log(2)+1) 좀 남긴하는데

[익명(59.24)]

나는 t_size = 1; while (t_size < N) { t_size <<= 1; } 만큼 할당해

[익명(59.24)]

2*t_size+1만큼 ㅋㅋ

[익명(118.235)]

가장 가까운 2의 거듭제곱수 *2 인데 걍 *4하면 무조건 그것보다 큼

[익명(118.235)]

가장 차이가 많이 날때가 2^n +1이 가장 거듭제곱수에서 먼건데 ×2 하면 2^(n+1)+2로 그것보다 큰 거듭제곱수인 2^(n+1)보다 무조건 크니까 거기에 ×2를 또 하면 되는거지

[울댕별(mypuppystarpoo)]

정확한 수를 알고싶은 탐구심임

[익명(211.246)]

가장 가까운 2의 거듭제곱수 *2 맞음

[raker(rakerdam)]

ㅋㅋㅋㅋㅋ

[ㅋㅋㅋ(211.234)]

파워 4n