세그먼트 트리, 간격 트리, 이진 색인 트리 및 범위 트리의 차이점은 다음과 같습니다.
- 핵심 아이디어 / 정의
- 응용
- 더 높은 차원 / 공간 소비에서의 성능 / 순서
단지 정의를 제공하지 마십시오.
답변
이러한 모든 데이터 구조는 다른 문제를 해결하는 데 사용됩니다.
- 세그먼트 트리는 간격을 저장하고 ” 이 간격 중 주어진 지점을 포함하는 간격 “쿼리에 대해 최적화됩니다 .
- 간격 트리도 간격을 저장하지만 ” 이 간격 중 주어진 간격과 어떤 간격이 겹치는 지 “쿼리에 최적화되어 있습니다. 세그먼트 트리와 유사한 포인트 쿼리에도 사용할 수 있습니다.
- 범위 트리는 점을 저장하고 ” 주어진 간격 내에있는 점 “쿼리에 최적화되어 있습니다.
- 이진 인덱싱 된 트리는 인덱스 당 항목 수를 저장하고 ” 인덱스 m과 n 사이에 몇 개의 항목이 있는지 “최적화 합니다.
1 차원의 성능 / 공간 소비 :
- 세그먼트 트리 -O (n logn) 전처리 시간, O (k + logn) 쿼리 시간, O (n logn) 공간
- 간격 트리 -O (n logn) 전처리 시간, O (k + logn) 쿼리 시간, O (n) 공간
- 범위 트리 -O (n logn) 전처리 시간, O (k + logn) 쿼리 시간, O (n) 공간
- 이진 색인 트리 -O (n logn) 전처리 시간, O (logn) 쿼리 시간, O (n) 공간
(k는보고 된 결과의 수입니다).
사용 시나리오에 데이터 변경 및 쿼리가 모두 포함된다는 점에서 모든 데이터 구조는 동적 일 수 있습니다.
- 세그먼트 트리 -간격은 O (로그온) 시간에 추가 / 삭제 가능 ( 여기 참조 )
- 간격 트리 -O (로그온) 시간에 간격을 추가 / 삭제할 수 있습니다
- 범위 트리 -O (로그온) 시간에 새 포인트를 추가 / 삭제할 수 있습니다 ( 여기 참조 ).
- 이진 색인 트리 – 색인 당 항목 수를 O (로그온) 시간으로 늘릴 수 있습니다
더 큰 치수 (d> 1) :
- 세그먼트 트리 -O (n (logn) ^ d) 전처리 시간, O (k + (logn) ^ d) 쿼리 시간, O (n (logn) ^ (d-1)) 공간
- 간격 트리 -O (n logn) 전처리 시간, O (k + (logn) ^ d) 쿼리 시간, O (n logn) 공간
- 범위 트리 -O (n (logn) ^ d) 전처리 시간, O (k + (logn) ^ d) 쿼리 시간, O (n (logn) ^ (d-1))) 공간
- 이진 색인 트리 -O (n (logn) ^ d) 전처리 시간, O ((logn) ^ d) 쿼리 시간, O (n (logn) ^ d) 공간
답변
Lior의 답변 에 아무것도 추가 할 수는 없지만 좋은 테이블로 할 수있는 것처럼 보입니다.
한 차원
k
보고 된 결과의 수
| | Segment | Interval | Range | Indexed |
|--------------|--------------:|-----------:|---------------:|----------:|
|Preprocessing | n logn | n logn | n logn | n logn |
|Query | k+logn | k+logn | k+logn | logn |
|Space | n logn | n | n | n |
| | | | | |
|Insert/Delete | logn | logn | logn | logn |
더 높은 차원
d > 1
| | Segment | Interval | Range | Indexed |
|--------------|--------------:|-----------:|---------------:|----------:|
|Preprocessing | n(logn)^d | n logn | n(logn)^d | n(logn)^d |
|Query | k+(logn)^d | k+(logn)^d | k+(logn)^d | (logn)^d |
|Space | n(logn)^(d-1) | n logn | n(logn)^(d-1)) | n(logn)^d |
이 테이블은 Github Formatted Markdown으로 생성됩니다 . 테이블을 멋지게 포맷하려면 이 요점을 참조하십시오 .