문제 축

먼저 “문자열 경로냐, 인덱스 구간이냐”를 고른다

트라이와 구간 트리는 둘 다 트리지만, 노드가 대표하는 상태 공간이 다릅니다.

첫 질문 질의가 글자 경로를 따라가나, 배열 범위를 쪼개나?

Trie: 한 글자가 한 단계

c-a 경로를 공유한 뒤 r과 t로 갈라지는 트라이 c a r t

검색어, 접두사, 자동완성처럼 같은 prefix를 공유하면 트라이가 맞습니다.

문자 접두사 경로

Segment Tree: 한 구간이 한 노드

0부터 7까지의 구간을 반씩 나누는 세그먼트 트리 [0,7] [0,3] [4,7] [0,1] [2,3] [4,5] [6,7]

구간 합, 최솟값, 최댓값처럼 범위 집계가 반복되면 구간 트리가 맞습니다.

인덱스 범위 집계

핵심 자료구조 이름보다 먼저 “노드가 무엇을 대표하는가”를 확인합니다.