문자 하나를 간선처럼 따라가며 단어 경로를 만듭니다
cat과 car는 c-a 접두사 노드를 공유합니다.
트라이/구간 트리
insert("cat"), startsWith("ca"), [l,r], 점 업데이트는 문자열 경로와 배열 구간을 나누는 대표 패턴입니다.
Trie 접두사 경로 확인
단어 끝 표시와 접두사 존재를 구분해야 합니다.
세그먼트 트리 저장
[0,7]에서 [0,3], [4,7]로 내려가며 필요한 구간만 봅니다.
세그먼트 트리 갱신
O(log N)으로 여러 질의 사이의 변경을 반영합니다.
문자열 길이
트라이 연산 비용은 단어 길이 L에 비례합니다.
질의 빈도
구간 질의가 많고 업데이트가 섞이면 세그먼트 트리가 빛납니다.
인덱싱
0-based와 1-based 구간 경계를 섞으면 한 칸 오류가 자주
납니다.