축과 갱신 빈도가 선택 비용을 결정한다
같은 정답이라도 질의가 반복되는 축과 업데이트 여부에 따라 병목이 달라집니다.
질의 축 / 갱신
정적 또는 적은 갱신
빈번한 갱신
문자열 prefix
Trie
삽입 후 search, startsWith를 O(L)에 반복
Trie + 카운트
단어 수, 후보 수를 노드에 같이 유지
인덱스 구간
누적합 먼저 검토
갱신이 없으면 prefix sum이 더 단순
Segment Tree
query와 update를 모두 O(log N)에 처리
Trie 비용 문자열 길이 L이 깊이입니다.
Segment 비용 배열 길이 N의 로그 높이만 방문합니다.
공간 비용 Trie는 문자 수, Segment Tree는 배열 크기에 비례합니다.
판단 순서 구간 질의라도 갱신이 없다면 누적합이 먼저이고, 갱신이 반복될 때 세그먼트 트리가 빛납니다.