PROBLEM AXIS

자료구조 선택은 트리 모양이 아니라 분할 축으로 결정한다

트라이는 문자열 접두사를, 구간 트리는 배열 인덱스 범위를 쪼갭니다. 먼저 질의가 어느 축을 따라 움직이는지 표시합니다.

첫 질문문제의 상태가 문자 경로인가, 인덱스 구간인가?

Trie 루트에서 문자 하나씩 내려가며 접두사를 공유합니다. 자동완성, 단어 검색, prefix count처럼 문자열 경로 질의에 맞습니다.

문자접두사경로

Segment Tree 배열 범위를 반씩 나누고 각 노드에 합, 최댓값 같은 집계 결과를 저장합니다. 구간 질의와 점 업데이트에 맞습니다.

인덱스범위집계

검증: 문자열 질의는 `startsWith`, 수열 질의는 `[l, r]` 구간 합처럼 대표 연산을 하나씩 적어 보면 선택 오류가 바로 드러납니다.