문자열 접두사인가?
검색어가 글자 단위로 내려가면 Trie가 후보입니다.
자료구조 이름보다 질의 축을 먼저 말한다
문제를 읽고 아래 세 질문에 답하면 트라이와 세그먼트 트리의 선택이 거의 결정됩니다.
구간 집계인가?
배열 [l, r]의 합/최솟값/최댓값이면 Segment Tree를 봅니다.
갱신이 반복되는가?
값 변경 뒤 질의가 계속되면 부모 집계 재계산이 필요합니다.
Trie를 고르는 문장
startsWith("ca"), 자동완성, 금칙어 prefix, 사전 검색
Segment Tree를 고르는 문장
query(l,r), 점 업데이트, 구간 합/최솟값/최댓값 반복
한 줄 결론 트라이는 “문자 경로를 압축”하고, 세그먼트 트리는 “인덱스 구간 집계를 압축”합니다.