문자열 접두사
자동완성, 사전 검색, 금칙어 탐지처럼 접두사 공유가 핵심이면 노드가 문자 하나씩 내려가는 트라이가 자연스럽다.
트리 구조 선택 기준
트라이와 구간 트리는 분할 기준이 다르다
트라이는 문자열의 문자 경로를 따라가고, 구간 트리는 배열 인덱스를 반씩 나누어 range query와 point update를 처리한다.
문자 경로인지 인덱스 범위인지가 갈림길
query shape구간 집계
합, 최소/최대, gcd처럼 결합 가능한 값이 인덱스 범위로 들어오면 구간 트리를 쓴다.
검증 질문
질의 단위가 글자 길이 L인지, 배열 크기 N의 구간인지 먼저 표시하면 구조 선택이 흔들리지 않는다.
복잡도 단위
트라이는 O(L), 구간 트리는 O(log N)으로 비교 단위가 달라 직접 우열을 매기면 틀린다.
질의 축 확인분할 기준 선택연산 구현prefix·range 반례
트라이는 빈 문자열·접두어 중복, 구간 트리는 0-index 경계와 lazy propagation 누락을 반례로 먼저 확인한다.