간격, 세그먼트, 펜윅 나무가 같은가요?

Question

오늘 fenwick 나무 (바이너리 색인화 된 나무)에 관한 강의를 들었고 선생님은이 나무가 간격 및 세그먼트 나무의 일반화라고하지만이 세 가지 데이터 구조에 대한 구현이 다릅니다라고 교사는 말합니다. 이 확인은 맞습니까? 그리고 왜?

Answer 1

아무 것도 일반화 된 binary indexed trees을 들어 본 적이 없습니다. 확실히 interval trees 및 segment trees의 일반화가 아닙니다. 나는 당신이 이것을 납득시키는 링크를 따르는 것이 좋습니다. 이 나무보다 더

는 그가 잘못, 간격 및 세그먼트 나무

"이 나무"에서 선생님이 "이진 인덱스 나무"를 의미하는 경우

의 일반화이다.

하지만,이 세 가지 데이터 구조의 내 구현

는 선생님은하지 않을 것이라고 말했다 결코, 그들은 다른 물론

다릅니다. 그는 방금 하나가 다른 하나의 일반화라고 말했습니다 (사실이 아니지만 여전히 그렇습니다). 어쨌든, 구현은 다른 것으로 생각됩니다. 그 같은 일때문에 같은 구현을 할 것이다 무엇

은 바이너리 인덱스 나무와 펜윅 나무입니다.

Answer 2

다른 사람들이 이러한 용어를 혼합해야하지만 다음 분류는 합리적입니다.

펜윅 나무/이진 인덱스 트리link

당신이 접두사 금액 (또한 누적 합계)를 저장하는 이진 표현에 단일 배열 및 운영을 사용하는 일. 요소는 monoid의 멤버가 될 수 있습니다.

범위 트리link

각 노드가 주어진 범위의 하위 범위를 나타내는 트리의 가족 말할 [0, N]. 간격에서 연관 연산을 계산하는 데 사용됩니다. 당신이 실제 간격을 저장

간격 트리link

나무. 가장 일반적으로 중간 점을 잡고 노드에서 교차 간격을 유지하고 점의 왼쪽과 오른쪽 간격으로 프로세스를 반복합니다. 잎이 가능한 연속 공간에서 초 간격보다는 이산 높은 노드입니다 범위 트리와 유사

세그먼트 트리link

는 초 간격의 조합입니다. 포인트 포함 여부를 확인하는 데 사용됩니다.