오답은 구조보다 경계와 종료 조건에서 난다
트라이는 “완전 단어인지”, 세그먼트 트리는 “[l,r]을 어떻게 나누는지”를 작은 입력으로 먼저 검산한다.
| 구조 | 반례 입력 | 틀린 이유 | 고정 규칙 |
|---|---|---|---|
| Trie terminal | insert("car"), search("ca") | prefix를 완전 단어로 처리 | 마지막 노드의 end 표시 확인 |
| Trie normalize | "Cat" vs "cat" | 삽입·검색 변환이 다름 | insert/search 전에 같은 정규화 |
| Segment split | query(1,3) | mid 포함 범위를 겹치거나 빠뜨림 | [l,mid] / [mid+1,r]로 분리 |
| Parent update | update(2,10) | 리프만 바꾸고 부모 합을 방치 | parent = left + right 재계산 |
공통 기준: 가장 작은 입력에서 “끝 표시, 정규화, 구간 분할, 부모 갱신”을 먼저 깨뜨려 본다.