Split Axis

트라이와 세그먼트 트리

두 구조 모두 트리 모양을 갖지만 상태 단위가 다릅니다. 질의가 접두사를 묻는지, 구간 집계를 묻는지 먼저 고정하면 구현 선택과 반례가 함께 정리됩니다.

Trie

문자열을 접두사 경로로 저장

상태 단위

루트에서 현재 노드까지의 문자 prefix

대표 질의

완전 단어 검색, 자동완성, prefix 존재 여부

필수 반례

`car`와 `care`처럼 종료 표식이 갈리는 입력

Segment Tree

배열을 절반 구간으로 나눠 집계

상태 단위

노드가 대표하는 인덱스 범위 `[l, r]`

대표 질의

구간 합, 구간 최솟값, 점 업데이트 후 재질의

필수 반례

왼쪽 끝, 오른쪽 끝, `mid` 경계가 겹치는 질의

memory

문자 집합과 배열 크기

트라이는 전체 문자 수, 세그먼트 트리는 보통 `4N` 배열 비용을 예상합니다.

update

갱신 빈도

문자열 추가가 많은지, 점 업데이트와 구간 질의가 반복되는지 분리합니다.

범위

과설계 여부

단순 1회 검색이나 1회 합산이면 더 작은 구조가 충분한지 확인합니다.