접두사와 단어 종료를 분리
트라이는 문자마다 노드를 내려가며, 접두사 존재와 완전 단어 여부를 다른 표식으로 관리합니다.
트라이와 구간 트리는 질의 축이 다를 때 고른다
트라이는 문자열 경로를, 세그먼트 트리는 인덱스 구간을 다룹니다. 질의가 어떤 축을 따라 쪼개지는지 먼저 봐야 합니다.
구간을 반씩 나눠 합친다
세그먼트 트리는 질의 범위가 노드 구간과 겹치는 방식으로 합을 빠르게 계산합니다.
변경 전파 비용 검토
점 업데이트가 자주 있으면 구간 트리의 O(log N) 갱신이 단순 누적 배열보다 유리해집니다.
구조 도입 전 질문
문자열접두사 검색, 자동완성, 단어 존재처럼 문자 경로가 핵심인지
확인합니다.
정적 구간업데이트가 없다면 누적합으로 충분한지 먼저 비교합니다.
동적 구간질의와 수정이 섞이면 경계 포함 규칙과 재귀 반환을
테스트합니다.