접두사 공유 활용
공통 prefix가 많고 단어 존재를 물으면 트라이 노드 경로가 자연스럽습니다.
트라이는 문자 경로, 세그트리는 구간 상태 압축
문자열 접두사와 배열 구간 질의는 모두 트리처럼 보이지만 쪼개는 기준과 업데이트 비용이 완전히 다릅니다.
범위 값을 노드에 저장
합, 최소, 최대처럼 범위 값을 반복해서 묻는다면 세그먼트 트리를 봅니다.
영향 경로만 갱신
값이 바뀌는 위치에서 루트까지 영향 범위만 다시 계산합니다.
상태 단위
문자 하나인지 구간 절반인지 먼저 정하면 노드 의미가 흔들리지
않습니다.
인덱스 경계
0/1 기반, 반열림/닫힌 구간을 예제 하나로 고정합니다.
메모리
알파벳 크기와 배열 길이에 따라 압축 표현을 검토합니다.