상태 단위

트라이 노드는 접두사, 세그트리 노드는 구간이다

두 구조를 고르는 핵심은 저장 값이 아니라 “어떤 상태를 한 노드로 압축하는가”입니다.

Trie node = prefix 상태

루트에서 현재 노드까지의 글자열이 검색 상태가 됩니다.

c와 a를 지나면 prefix ca 상태가 된다 root c a r 현재 상태: prefix "ca"
질의startsWith("ca")
방문c -> a 두 단계
검산end 플래그로 완전 단어 분리

Segment node = interval 상태

각 노드는 배열 일부 구간과 그 구간의 집계값을 대표합니다.

구간 1부터 3까지의 합을 여러 노드에서 모은다 2 1 3 4 5 [1,3] = 8 필요 구간만 합친다
질의query(1, 3)
방문겹치는 구간 노드만 선택
검산update 후 부모 집계 재계산

정리 트라이는 경로 상태를 줄이고, 세그먼트 트리는 구간 집계를 줄입니다.