[algorithm] 세그먼트 트리, 인터벌 트리, 이진 인덱스 트리 및 범위 트리의 차이점은 무엇입니까?

Program / 글쓴이

세그먼트 트리, 간격 트리, 이진 색인 트리 및 범위 트리의 차이점은 다음과 같습니다.

  • 핵심 아이디어 / 정의
  • 응용
  • 더 높은 차원 / 공간 소비에서의 성능 / 순서

단지 정의를 제공하지 마십시오.

답변

이러한 모든 데이터 구조는 다른 문제를 해결하는 데 사용됩니다.

  • 세그먼트 트리는 간격을 저장하고 ” 이 간격 중 주어진 지점을 포함하는 간격 “쿼리에 대해 최적화됩니다 .
  • 간격 트리도 간격을 저장하지만 ” 이 간격 중 주어진 간격과 어떤 간격이 겹치는 지 “쿼리에 최적화되어 있습니다. 세그먼트 트리와 유사한 포인트 쿼리에도 사용할 수 있습니다.
  • 범위 트리는 점을 저장하고 ” 주어진 간격 내에있는 점 “쿼리에 최적화되어 있습니다.
  • 이진 인덱싱 된 트리는 인덱스 당 항목 수를 저장하고 ” 인덱스 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으로 생성됩니다 . 테이블을 멋지게 포맷하려면 이 요점을 참조하십시오 .

답변