문자열은 경로가 곧 상태
c
->
a
->
r
t
같은 트리라도 “노드가 뜻하는 것”이 다르다
트라이는 접두사 상태를 저장하고, 구간 트리는 배열 구간의 집계값을 저장합니다.
비교 축
Trie
Segment Tree
노드 의미
루트에서 여기까지의 prefix
예: c -> a 노드는 “ca” 상태
하나의 인덱스 범위
예: [0,3] 노드는 네 칸의 합
자식 의미
다음 문자 후보
r, t처럼 다음 글자로 분기
왼쪽 절반과 오른쪽 절반
mid 기준으로 범위를 둘로 나눔
대표 질의
search / startsWith
문자 길이 L만큼 내려감
query / update
겹치는 구간만 방문
복잡도 단위
O(L)
L은 문자열 길이
O(log N)
N은 배열 길이
배열은 범위가 곧 상태
주의 O(L)과 O(log N)은 비교 단위가 다르므로, 먼저 입력이 문자열 축인지 인덱스 축인지 고정합니다.