세그먼트 트리

컴퓨터 공학에서, 통계 트리로도 알려진 세그먼트 트리는 간격, 즉 세그먼트에 대한 정보를 저장하는 데 사용되는 트리 데이터 구조다.저장된 세그먼트 중 지정된 점을 포함하는 세그먼트를 쿼리할 수 있다.그것은, 원칙적으로, 정적인 구조다. 즉, 한번 지어지면 수정할 수 없는 구조다.유사한 데이터 구조가 구간 트리다.

n개의 간격의 $집합$ I에 대한 세그먼트 트리는 O(n log n) 저장소를 사용하며 O(n log n) 시간에 빌드할 수 있다.세그먼트 트리는 시간 O(log n + k), k는 검색된 간격 또는 세그먼트 수입니다.^[1]

세그먼트 트리의 적용은 컴퓨터 기하학, 지리 정보 시스템 및 기계 학습 영역에 있다.

세그먼트 트리는 더 높은 차원 공간으로 일반화할 수 있다.

구조설명

이 절에서는 1차원 공간에서 세그먼트 트리의 구조를 설명한다.

S를 구간 또는 세그먼트의 집합으로 합시다.p₁, p₂, ..., p는_m 왼쪽에서 오른쪽으로 정렬된 구별되는 간격 끝점의 목록이다.그러한 점들에 의해 유도된 실제 선의 분할을 고려한다.이 분할 영역을 기본 간격이라고 한다.따라서 기본 간격은 왼쪽에서 오른쪽으로:

{\displaystyle(-\infit,p_{1}), [p_{1},p_{1},(p_{1}, p_{2}), [p_{2},\p_{m-1},p_{m}],[p_{m},+\ft )}}

즉, 기본 간격 목록은 두 개의 연속된 끝점 p와_i p 사이의_i+1 열린 간격으로 구성되며, 닫힌 간격은 단일 끝점으로 구성된다.질의에 대한 대답이 반드시 기본 간격과 그 끝점의 내부에서는 동일하지 않기 때문에 단일 점들은 그 자체로 구간으로 취급된다.^[2]

세그먼트 트리의 구조에 대한 그래픽 예제.이 인스턴스는 하단에 표시된 세그먼트에 대해 작성된다.

구간 또는 세그먼트의 $I$ 집합에 따라 $I$ 에 대한 세그먼트 트리 T는 다음과 같이 구성된다.

T는 이진수다.
그것의 잎은 $I$ 의 엔드포인트에 의해 유도된 기본적인 간격에 순서대로 대응한다: 가장 왼쪽 잎은 가장 왼쪽 간격에 해당한다.잎 v에 해당하는 기본 간격은 Int(v)로 표시된다.
T의 내부 노드는 기본 구간의 결합인 간격에 해당한다. 노드 N에 해당하는 간격 Int(N)는 N에 뿌리를 둔 나무의 잎에 해당하는 구간의 결합이다.그것은 Int(N)가 두 자녀의 간격을 합친 것임을 암시한다.
T의 각 노드 또는 리프 V는 간격 Int(v)와 간격 집합을 일부 데이터 구조에 저장한다.노드 v의 이 표준 하위 집합은 [x, x′]가 Int(v)를 포함하고 Int(parent(v)를 포함하지 않는 $I$ 의 간격[x, x′]을 포함한다.즉, T의 각 노드는 그 간격을 통하여 확장되는 세그먼트를 저장하지만, 상위 노드의 간격은 확장하지 않는다.^[3]

스토리지 요구 사항

이 절은 1차원 공간에 있는 세그먼트 트리의 저장 비용을 분석한다.

n개 간격으로 설정된 $I$ 의 세그먼트 트리 T는 O(n log n) 저장소를 사용한다.

보조정리 — $I$ 의 임의 간격[x, x′]은 동일한 깊이에서 최대 두 개의 노드에 대해 표준 집합에 저장된다.

증명

v₁, v₂, v를₃ 동일한 깊이의 3개 노드로, 왼쪽에서 오른쪽으로 번호를 매기고 p(v)를 지정된 노드 v의 상위 노드로 한다. [x, x x]가 v와₁ v에₃ 저장된다고 가정한다.즉 [x, x x]은 Int(v₁)의 왼쪽 끝점에서 Int(v₃)의 오른쪽 끝점까지의 전체 간격을 의미한다.특정 수준의 모든 세그먼트는 겹치지 않고 왼쪽에서 오른쪽으로 정렬된다는 점에 유의하십시오. 이는 잎을 포함하는 레벨에 대한 시공에 의해 해당되며, 인접한 세그먼트 쌍을 결합하여 어떤 레벨에서 위 레벨로 이동할 때 속성이 손실되지 않는다.이제 부모(v₂) = 부모(v₁) 또는 전자는 후자의 오른쪽에 있다(나무의 에지는 교차하지 않는다).첫 번째 경우, Int(v₂)의 가장 왼쪽 끝점은 Int(v₁)의 가장 왼쪽 끝점과 같고, 두 번째 경우 Int(v₂)의 가장 왼쪽 끝점은 Int(parent(v₁))의 가장 오른쪽이며, 따라서 Int(v₁)의 가장 오른쪽이기도 하다.두 경우 모두 Int(parent(v₂))의 맨 왼쪽₁ 지점 또는 오른쪽에서 Int(v)가 시작된다.유사한 추론은 Int(parent(v₂)가 Int(v₃)의 가장 오른쪽 또는 왼쪽에서 끝난다는 것을 보여준다.따라서 Int(parent(v₂)는 [x, x,]에 포함되어야 하므로 [x, x′]는 v에₂ 저장되지 않는다.

내

가 가지고 있는 세트에는 최대 4n + 1개의 기본 간격이 있다.T는 최대 4n + 1잎이 있는 이항균형 나무이기 때문에 높이는 O(log n)이다.임의의 간격은 트리의 지정된 깊이에 최대 두 번 저장되므로, 총 저장량은 O(n log n)이다.^[4]

건설

이 절에서는 1차원 공간에서 세그먼트 트리를 구성하는 방법을 설명한다.

세그먼트 $I$ 집합의 세그먼트 트리는 다음과 같이 작성할 수 있다.첫째, $I$ 에 있는 구간의 끝점이 정렬된다.그 기본적인 간격은 그것으로부터 얻어진다.그런 다음, 기본 간격에 따라 균형 잡힌 이진 트리가 생성되며, 각 노드 v에 대해 그것이 나타내는 간격 Int(v)를 결정한다.노드에 대한 표준 하위 세트를 계산해야 한다.이를 위해 $I$ 의 간격을 하나씩 세그먼트 트리에 삽입한다.X = [x, x′] 간격은 다음 절차를 사용하여 T에 뿌리를 둔 하위 트리에 삽입할 수 있다.^[5]

X에 Int(T)가 포함되어 있으면 X를 T에 저장하고 끝내십시오.
기타:
- X가 T의 왼쪽 자식의 간격을 교차하는 경우, 그 자식에 X를 재귀적으로 삽입한다.
- X가 T의 오른쪽 자식의 간격을 교차하는 경우, 그 자식에 X를 재귀적으로 삽입한다.

전체 시공 작업은 O(n log n) 시간이 소요되며, n은 $I$ 의 세그먼트 수가 된다.

증명

엔드포인트를 정렬하려면 O(n log n)가 필요하다.정렬된 엔드포인트에서 균형 잡힌 이진 트리를 만드는 것은 n에 선형 시간이 걸린다.

X = [x, x x] 구간을 트리에 삽입하면 O(log n) 비용이 든다.

증명

모든 노드를 방문하는 데는 일정한 시간이 소요된다(연계된 목록과 같은 단순한 데이터 구조에 표준 하위 집합이 저장된다고 가정).노드 v를 방문하면 v에 X를 저장하거나 Int(v)에 X의 끝점이 포함되어 있다.위에서 증명했듯이, 간격은 나무의 각 레벨에 최대 두 번 저장된다.또한 각 수준에서 해당 간격이 x를 포함하는 노드와 x를 포함하는 노드가 한 개씩 있다.그래서 레벨당 최대 4개의 노드를 방문한다.O(log n) 레벨이 있기 때문에 삽입의 총 비용은 O(log n)이다.^[1]

질의

이 절에서는 1차원 공간에서 세그먼트 트리의 쿼리 작동을 설명한다.

세그먼트 트리에 대한 쿼리, 포인트 q_x(트리의 잎 중 하나여야 함)를 수신하고 포인트 q를_x 포함하는 저장된 모든 세그먼트 목록을 검색한다.

공식적으로 명시됨. 노드(하위) v와 쿼리 지점 q가_x 주어진 경우, 쿼리는 다음 알고리즘을 사용하여 수행할 수 있다.

$I (v$ ) 단위로 모든 간격을 보고한다 $.$
v가 리프(leaf)가 아닌 경우:
- q가_x Int(v의 왼쪽 하위)에 있는 경우
  - v의 왼쪽 하위 항목에서 쿼리를 수행하십시오.
- q가_x Int(v의 오른쪽 하위)에 있는 경우
  - v의 오른쪽 하위 항목에서 쿼리를 수행하십시오.

n개의 구간을 포함하는 세그먼트 트리에서 주어진 쿼리 포인트를 포함하는 구간은 O(log n + k) 시간에 보고할 수 있으며, 여기서 k는 보고된 구간 수입니다.

증명

쿼리 알고리즘은 트리의 레벨당 한 개의 노드를 방문하므로 O(log n) 노드는 총합이다.한편, 노드 v에서 $I$ 의 세그먼트는 O(1 + k_v) 시간에 보고되며, 여기서 k는_v 노드 v에서 보고된 간격 수입니다.v가 방문한 모든 노드에 대한 모든_v k의 합은 보고된 세그먼트 수인 k이다.^[4]

상위차원에 대한 일반화

세그먼트 트리는 다단계 세그먼트 트리의 형태로 더 높은 차원 공간으로 일반화할 수 있다.고차원 버전에서 세그먼트 트리는 축-병렬(하이퍼-퍼-)직사각형 컬렉션을 저장하며, 주어진 쿼리 포인트를 포함하는 직사각형을 검색할 수 있다.구조는 O(n log^d n) 저장소를 사용하며, O(log^d n)의 질의에 응답한다.

부분 계단식 계단식 사용은 로그 인자에 의해 바인딩된 쿼리 시간을 낮춘다.관련 구조물의 가장 깊은 수준에서 구간 트리를 사용하면 로그 인자에 의해 바인딩된 저장소를 낮출 수 있다.^[6]

메모들

주어진 점을 포함하는 모든 간격을 묻는 질의를 찌르는 질의를 흔히 일컫는다.^[7]

세그먼트 트리는 간격 트리의 O(n)에 대한 O(n log n) 저장 요구 사항이 높기 때문에 한 차원 범위 쿼리에 대한 간격 트리보다 효율성이 낮다.세그먼트 트리의 중요성은 각 노드의 표준 서브셋 내의 세그먼트를 임의의 방식으로 저장할 수 있다는 것이다.^[7]

엔드포인트가 작은 정수 범위(예: [1, …,O(n)] 범위)인 n개의 간격에 대해, 주어진 쿼리 포인트를 포함하는 모든 k개의 간격을 보고하기 위한 선형 사전 처리 시간과 쿼리 시간 O(1 + k)로 최적의 데이터 구조가^[which?] 존재한다.

세그먼트 트리의 또 다른 장점은 쿼리 카운트에 쉽게 적응할 수 있다는 것이다. 즉, 세그먼트를 직접 보고하는 대신 특정 지점을 포함하는 세그먼트 수를 보고하는 것이다.표준 하위 집합에 간격을 저장하는 대신 단순히 개수를 저장할 수 있다.이러한 세그먼트 트리는 선형 저장소를 사용하며, O(log n) 조회 시간이 필요하므로 최적이다.^[8]

구간 트리와 우선순위 검색 트리의 고차원 버전은 존재하지 않는다. 즉, 더 높은 차원에서도 유사한 문제를 해결하는 이러한 구조의 명확한 확장이 없다.그러나 이 구조물은 세그먼트 트리의 관련 구조로 사용될 수 있다.^[6]

역사

세그먼트 트리는 1977년 존 벤틀리에 의해 발명되었다; "클리의 직사각형 문제 해결"에서.^[7]

참조

^ ^a ^b (de Berg 등). 2000, 227 페이지)
^ (de Berg 등). 2000, 페이지 224)
^ (de Berg 등). 2000, 페이지 225–226)
^ ^a ^b (de Berg 등). 2000, 226 페이지)
^ (de Berg 등). 2000, 페이지 226–227)
^ ^a ^b (de Berg 등). 2000, 230 페이지)
^ ^a ^b ^c (de Berg 등). 2000, 229 페이지)
^ (de Berg 등). 2000, 페이지 229–230)

출처 인용

de Berg, Mark; van Kreveld, Marc; Overmars, Mark; Schwarzkopf, Otfried (2000). "More Geometric Data Structures". Computational Geometry: algorithms and applications (2nd ed.). Springer-Verlag Berlin Heidelberg New York. doi:10.1007/978-3-540-77974-2. ISBN 3-540-65620-0.
http://www.cs.nthu.edu.tw/~wkhon/ds/ds10/dsf/ss6.pdf

외부 링크

세그먼트 트리 – CP-알고리즘

[Schwarzkopf1-1] (de Berg 등). 2000, 227 페이지)

[2] (de Berg 등). 2000, 페이지 224)

[3] (de Berg 등). 2000, 페이지 225–226)

[Schwarzkopf2-4] (de Berg 등). 2000, 226 페이지)

[5] (de Berg 등). 2000, 페이지 226–227)

[Schwarzkopf3-6] (de Berg 등). 2000, 230 페이지)

[Schwarzkopf4-7] (de Berg 등). 2000, 229 페이지)

[8] (de Berg 등). 2000, 페이지 229–230)

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

v t 트리 데이터 구조
나무 검색 (이중 세트/관련 배열)	2–3 2–3–4 AA (a,b) AVL B B+ B* B^x (최적) 이진 검색 춤 HTree 간격 오더통계 (좌편향) 빨강-검은색 희생양 스플레이 T 트레프 UB 무게균형
힙스	이진수 이항체 브로달 피보나치 좌익 페어링 스큐 판 엠드 보아스 약한
시도하다	씨트리 C-트리(압축 ADT) 해시 라딕스 접미사 3차 검색 X-fast Y-fast
공간 데이터 분할 트리	볼 BK BSP 카르테시안 힐베르트 R k-d(일반적으로 k-d) M 미터법 MVP 옥트리 PH 우선 순위 R 쿼드 R R+ R* 세그먼트 부사장 X
다른 나무들	커버 지수적 펜윅 손가락 프랙탈 트리 지수 퓨전 해시 캘린더 아이 디스턴스 케이애리 왼손잡이 우시블링 링크/컷 로그 구조 병합 머클 p q. 범위 SPQR 톱

Search