[알고리즘] 세그먼트 트리 ( Segment Tree ) #1 개념 소개

이전의 포스팅에서 분할 정복(Divide & Conquer)과 이진 검색(Binary Search)에 대한 내용을 소개했는데, 이 개념을 응용하여 구간 연산을 효율적으로 할 수 있도록 해주는 세그먼트 트리를 소개합니다.

 

세그먼트 트리 ( Segment Tree )

Segment Tree는 효율적으로 구간 쿼리 연산을 수행하기 위한 자료 구조이며, 다양한 알고리즘 문제나 데이터 구조에 유용하게 사용될 수 있는 강력한 도구입니다. 

주로 배열이나 리스트와 같은 선형 구조에서 구간에 대한 쿼리를 빠르게 처리할 때 사용됩니다. 예를 들면, 배열의 특정 구간의 합을 구하거나 최솟값, 최댓값을 찾는 등의 연산을 빠르게 수행할 수 있습니다.

연산을 빠르게 수행할 수 있는 이유는 구간별 필요한 연산을 미리 해두고 결과만 가져올 수 있기 때문인데, 미리 연산을 하기 때문에 데이터 양이 작은 경우는 큰 차이가 없겠지만, 한번의 데이터 입력 후 여러번 계산 결과가 필요한 경우는 연산 시간 없이 결과만을 가져오게 됩니다.

 

특징

Segment Tree의 구간 쿼리 연산은 주로 다음과 같은 종류가 있습니다.

• 구간 합 계산: 주어진 구간 내의 원소들의 합을 계산합니다.
• 최솟값/최댓값 찾기: 주어진 구간 내의 원소들 중에서 최솟값이나 최댓값을 찾습니다.
  ※ 구간내 가장 큰 값 2개, 가장 작은 값 2개 찾기 등도 응용해서 처리할 수 있기도 합니다.
• 구간 내 값 갱신: 주어진 구간 내의 원소들을 갱신하고, 구간에 대한 정보를 업데이트합니다.
  ※ 데이터가 많아지면 업데이트 할 때 시간이 걸릴 수 있는데, 이 부분도 응용을 한다면 업데이트 시간을 효과적으로 단축시킬 수 있습니다.

 

아래 그래프(출처:위키피디아) 에서 파란색 Leaf Node 가 실제 데이터가 되고, 빨간색 중간 Node 는 자식 Node 구간(하위 데이터)의 구간 결과 값이 됩니다. 최종 Root Node 는 전체 구간의 결과가 되는 구조입니다.

Segment Tree Sample in Wikipedia

 

설명

Segment Tree는 이진 트리로 구성되어 있으며, 각 노드는 배열의 구간을 나타냅니다.

 

다음과 같은 데이터가 정의되어 있고, 구간 합을 위한 세그먼트 트리를 만든다고 하면,

int _data[] = { 9, 11, 8, 3, 22, 12, 23, 45, 31, 36 };

 

이러한 트리가 완성됩니다.

 

완성된 Segment Tree

 

루트 노드는 전체 배열 데이터의 합인 sum[0:9] 의 값인 200 을 가지게 됩니다.

sum[0:7] 에 대한 구간을 구하고 싶다면, 해당되는 구간의 부모 노드의 값을 확인하게 됩니다.

 

각 내부 노드는 두 개의 자식 노드로 나누어진 구간을 표현하며, 리프 노드는 데이터의 배열의 각 원소(파란색 Node)를 나타냅니다. 이렇게 구성된 Segment Tree는 구간을 나타내는 노드에 대해서 하위 구간에 대한 연산 결과를 미리 계산하여 저장합니다.

Segment Tree를 구성하는 데에는 주로 재귀적인 방법을 사용하게 되고, Leaf Node 에는 데이터의 원소값을 할당하고, 구간별 중간 노드의 값은 해당 구간에 대한 연산 결과를 의미합니다.

 

시간복잡도

구간을 나누고 정보를 저장하므로, 데이터에 대해서 구간 연산이 완료(Build) 되면, 구간 쿼리 연산을 수행할 때에는 필요한 구간만큼만 탐색하고 그 결과만 확인합니다. 전체 구간을 탐색하는 것보다 강력하고 효율적이라고 할 수 있겠습니다.

Segment Tree는 구간 쿼리 연산을 수행하는 데에 O(logN)의 시간 복잡도를 가집니다.

구간의 크기가 N일 때, Segment Tree를 구성하는 데에는 O(N)의 시간이 소요되지만, 한 번 구성된 Segment Tree는 여러 구간 쿼리 연산에 사용할 수 있으므로 전체적으로는 효율적입니다.

 

See Also

기본적인 구현 방법은 아래에서 설명하도록 하겠습니다.

 

[알고리즘] 세그먼트 트리 ( Segment Tree ) #2 구현

[알고리즘] 세그먼트 트리 ( Segment Tree ) #2 구현

 

 

 

일부 데이터를 Update 하는 방법에 대해서는 별도로 추가하였으니 함께 확인하시면 좋을 것 같습니다.

 

[알고리즘] 세그먼트 트리 ( Segment Tree ) #3 Update

[알고리즘] 세그먼트 트리 ( Segment Tree ) #3 Update

 

이상입니다.