알고리즘 인덱스 트리, 세그먼트 트리

인덱스 트리 개념설명

https://beenii.tistory.com/156

 

세그먼트 트리 개념설명

https://minusi.tistory.com/entry/%EC%84%B8%EA%B7%B8%EB%A8%BC%ED%8A%B8-%ED%8A%B8%EB%A6%ACSegment-Tree-Index-Tree

 

인덱스 트리 vs 세그먼트 트리

인덱스 트리: 리프노드를 모두 채워서 만듦. 특정 인덱스(node)로 지정 탐색이 가능. 업데이트도 지정 업데이트 가능(리프노드부터 업데이트 가능)

세그먼트 트리: 필요한 리프노드만 채움. 불완전 트리라서 특정 인덱스(node)로 지정 탐색이 어려움. 업데이트도 지정 업데이트가 불가능(루트노드부터 업데이트 필요)

=> 문제에서 인덱스가 주어지는 경우 인덱스 트리를 사용하는 것이 용이

=> 구간 업데이트가 빈번한 경우 세그먼트 트리를 사용하는 것이 용이 (인덱스 트리는 시간초과 가능성)