구조 선택 뒤에는 작은 반례로 구현을 잠근다
선택이 맞아도 종료 표식, mid 경계, 부모 재계산이 틀리면 바로 오답이 됩니다.
검증 항목
통과 증거
실패 징후
Trie search
prefix와 word 분리
startsWith("ca")와 search("ca") 결과가 다를 수 있음
end 누락
"car"만 넣었는데 "ca"가 단어로 판정됨
Segment query
겹침 조건 3개
no overlap, full cover, split을 순서대로 처리
mid 겹침
[l, mid]와 [mid, r]처럼 구간이 겹침
Update
부모 재계산
update 후 query 결과가 즉시 바뀜
옛 집계값
리프만 바뀌고 루트 합이 그대로 남음
완전 단어
insert("car"), search("ca") == false
한 칸 구간
query(1,1), query(0,n-1)
갱신 반영
update(2,10) -> query(1,3)