분할 축 선택
문자열 검색과 자동완성은 prefix 경로, range sum/min/max는 구간 분할이 맞습니다.
decompose끝 표시 관리
트라이에서는 `app`과 `apple`처럼 한 단어가 다른 단어의 접두사일 수 있어 terminal flag가 필요합니다.
terminal구간 포함 판정
segment tree 질의는 완전 포함, 불포함, 부분 포함 세 케이스로 나뉩니다.
range병합 함수 고정
합, 최솟값, 최댓값, gcd처럼 노드 값을 합치는 함수가 associative해야 구간 분해가 안전합니다.
mergeTrie search
문자 경로가 존재하고 끝 표시가 있는지 확인
prefix 존재와 단어 존재는 서로 다른 질문입니다.
prefix
Segment query
구간 관계 세 케이스를 빠짐없이 처리
경계가 inclusive인지 exclusive인지 혼동하면 off-by-one이
납니다.
bounds
Update
leaf 변경 뒤 조상 값을 다시 병합
한 위치 변경이 루트까지 O(log N) 경로에 영향을 줍니다.
propagate