글 읽기 - 세그먼트 트리 구현 시 사이즈 결정하기 질문드립니다

aaadddggg 7년 전 0

원소의 갯수가 N이라 할 때

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

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

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

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

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

private static long init_segment(int node, int start, int end){
	if(start == end){
		segment[node] = values[start];
	}
	else{
		segment[node] = init_segment(node * 2, start, (start + end) / 2) + init_segment(node * 2 + 1, (start + end) / 2 + 1, end);
	}
	return segment[node];
}

ntopia 7년 전 1

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

중간에 빈틈이 생기죠?

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

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

aaadddggg 7년 전 0

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

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

문제

문제

출처

ICPC

세그먼트 트리 구현 시 사이즈 결정하기 질문드립니다

aaadddggg 7년 전 0

ntopia 7년 전 1

aaadddggg 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말