문자 하나가 한 단계
검색어, 접두사, 자동완성처럼 같은 prefix를 공유하는 문제가 자연스럽다.
트라이는 문자열 축, 세그먼트 트리는 인덱스 축을 쪼갠다
두 구조는 모두 트리지만 질의를 분해하는 기준이 다릅니다. 문제의 축을 먼저 고정하면 구현 선택이 안정됩니다.
구간 하나가 한 노드
합, 최솟값, 최댓값처럼 배열 범위를 쪼개 집계하는 문제가 잘 맞는다.
접두사인가문자 경로를 따라가면 트라이를 검토한다.
범위 질의인가인덱스 구간을 묻는다면 세그먼트 트리를 고른다.
업데이트가 잦은가점 갱신 뒤 질의가 반복되면 구간 트리가 강하다.
메모리 압박인가문자 집합이 크면 트라이 노드 수를 먼저 추정한다.
자동완성은 트라이, 동적 구간 합은 세그먼트 트리처럼 문제 문장을 구조의 분할 축으로 번역하는 습관이 핵심입니다.