Algorithm: Segment Tree

Segment Tree는 배열과 같은 자료구조에서 주어진 구간의 질의를 빠르게 처리하기 위해 사용되는 자료구조 이다.

Segment Tree는 트리구조를 사용하여 구간을 나누어 저장하며 각 노드는 자식노드들의 정보를 이용하여 자신의 정보를 계산한다.

다음은 segment tree 의 예제인데, 노드 내부의 숫자는 어디서부터 어디까지의 합을 나타내는지를 보여준다

Segment Tree

Segment Tree 에서 

    - 리프노드: 배열의 수 그 자체

    - 다른 노드: 왼쪽, 오른쪽 자식의 합

 

Segment Tree로 특정구간 [a,b] 의 합을 구하려면 다음을 점검한다.

• [a,b] 와 [left, right] 이 겹치지 않는다
  • do nothing
• [a,b] 가 [left, right] 을 포함
  • 미리 구해둔 [left, right]의 합을 사용
• [a,b] 를 [left, right]가 포함된다
  • 두 자식 노드에 대해 정확히 어느 노드가 [left,right]을 포함하는지 찾는다
• [a,b]가 [left, right]와 포함관계는 없지만 겹친다.
  • 두 자식 노드에 대해 정확히 어느 노드가 [left,right]을 포함하는지 찾는다

점 위의 선분 세기

• 이 알고리즘은 2차원 평면에서 주어진 선분들 중에서 특정 점 위에 몇 개의 선분이 있는지를 세는 문제이다
• 다음과 같은 선분들의 예가 있다
•  

• 이때, 시작과 끝 지점을 기준으로 2차원 평면을 나눈다. 
•  

• 이를 세그먼트 트리로 나타내면 다음과 같다
•  

• 각 노드는 해당 구간에 몇개의 선분이 있는가를 저장하고 있다.