[한방정리]삼성 SW검정 Pro 유형정리 #1

 인덱스 트리

구간합을 구하는 트리 하면 인덱스 트리, 세그먼트 트리, 펜윅 트리가 있습니다. 그 중 SW검정 Pro에 자주 출제되었던 인덱스 트리에 대해 알아보겠습니다.

 

인덱스 트리란 포화 이진트리 형태의 자료구조로 리프 노드에 내가 쓸 값들을 저장해두고, 부모들에는 해당 노드의 합들로 된 노드들을 구현해둔 트리입니다.

 

출제 유형은 아래와 같습니다.

반응형

유형		문제	비고
구간의 최소값 (RMQ)	구간의 최소값	[백준] 최솟값과 최댓값	기본적인 트리 질의 응답
	1 ~ N 까지 k칸 이내 건너 뛰기	[기출] 징검다리	구간의 최소값 변형 유형
	동순위 처리	[기출] 초밥	동순위 모아서 UPDATE
	MAX값 - MIN값	[기출] 인접한수의 차이	MAX TREE, MIN TREE 2개 사용
구간합 (RSQ)	구간합	[백준] 구간합구하기	기본적인 트리 질의 응답
	구간 변경	[백준] 구간합구하기2 [백준] 스위치	Lazy Propagation
	K번째 찾기	[기출] 도서관 [백준] 중앙값	구간합 변형 유형
	트리2개 + 이분탐색	[기출] 여행계획2	중복지점까지의 구간합
	이분탐색 왼쪽 구간합, 오른쪽 구간합	[기출] 물류창고	이분탐색 왼쪽 영역 구간합, 오른쪽 영역 구간합
값 Index로 사용	HashMap (Leaf 관리)	[기출] 부분수열최빈값 [기출] 별점 [기출] 물류창고	수의 개수에 비해 수치가 클 때 사용
오프라인 쿼리	오프라인 쿼리	[기출] 별점	값을 INDEX로 변환할 때 / INDEX 범위 넘어갈 때
리스트 + 이분탐색	값이 아닌 리스트로 관리 UPPERBOUND - LOWERBOUND	[기출] 교차점	교차점 개수 구하기

 

댓글과 공감 클릭은 더 좋은 글을 위한 응원이 됩니다.

 

관련글