세그먼트 트리의 구조

세그먼트 트리는 분할 정복 방식으로 배열을 다룬다. 먼저 전체 배열 의 합을 계산하여 저장한다. 그다음 배열을 반으로 나눠서 , 에 대한 합을 각각 계산하고 저장한다. 이 과정을 반복하여 길이가 1인 구간이 될 때까지 나눈다.

이러한 방식으로 만들어지는 구조는 이진 트리로 볼 수 있다. 트리의 루트는 이고, 리프 노드를 제외한 각 노드는 자식 노드를 두 개씩 가진다. 이러한 구조 때문에 ‘세그먼트 트리’라는 이름이 붙었으며, 실제 구현에서는 명시적으로 트리를 만들지 않더라도 논리적으로는 트리 구조이다 (구현은 이곳 참고).

다음 그림은 배열에 대해 세그먼트 트리를 구성한 예이다:

이 구조를 보면 세그먼트 트리는 선형적인 수의 노드만을 필요로 함을 알 수 있다. 첫 번째 레벨에는 하나의 노드(루트)가 있고, 두 번째 레벨에는 두 개, 세 번째에는 네 개… 이런 식으로 노드 수가 증가하다가, 리프 노드의 수가 이 된다. 최악의 경우 전체 노드 수는 이다.

배열 크기 이 2의 거듭제곱이 아닐 경우, 모든 레벨이 완전히 채워지지 않을 수 있다. 그림에서도 이러한 현상을 확인할 수 있다. 지금은 이 사실을 일단 무시해도 되지만, 구현 시에는 중요하게 작용한다.

세그먼트 트리의 높이는 이다. 루트에서 리프까지 내려갈 때마다 구간의 길이가 거의 절반씩 줄어들기 때문이다.

트리 구성

세그먼트 트리를 구성할 때는 먼저 다음 두 가지를 결정해야 한다:

1. 각 노드에 저장할 값: 예를 들어 합 세그먼트 트리에서는 구간 의 합을 저장한다.

2. 두 자식 노드를 병합하는 병합 연산: 예를 들어 합 세그먼트 트리에서는 구간 , 을 다루는 두 노드가 있다면, 이 둘의 값을 더하여 구간 의 값을 계산한다.

어떤 노드가 원래 배열의 값 하나만 포함하는 경우, 이를 리프 노드라고 한다. 이 리프 노드는 트리의 최하단에 위치하며, 노드 값은 배열 와 동일하다.

리프 노드부터 시작하여 각 노드에 값을 채워 넣음으로써 트리를 구성한다. 자식 노드의 값들을 병합 연산으로 합쳐가며 상위 노드의 값을 계산한다. 이 과정을 반복하면 루트 노드까지 올라가게 된다.

이 과정을 재귀적으로 설명하면 더 직관적이다. 리프가 아닌 노드에 대해 다음 절차를 따른다.

1. 두 자식 노드를 재귀적으로 구성한다.
2. 자식 노드 값을 병합 연산으로 합친다.

이렇게 루트부터 시작하여 전체 트리를 구성할 수 있다.

병합 연산이 시간에 가능하다고 하면, 전체 구성 시간은 이다. 병합 연산은 세그먼트 트리의 내부 노드 수만큼, 즉 번 호출된다.

합 질의

이제 구간 합 질의를 처리해 보자. 입력으로는 정수 , 이 주어지며, 구간 의 합을 에 계산해야 한다.

이를 위해 세그먼트 트리를 순회하며 미리 계산된 구간 합을 이용한다. 현재 노드가 구간 을 담당하고 있다고 하자. 가능한 경우는 다음의 세 가지이다.

1. 정확히 일치하는 경우

   이면 현재 노드의 값을 그대로 반환하면 된다.

2. 왼쪽 또는 오른쪽 자식의 구간에 완전히 포함되는 경우

   왼쪽 자식은 , 오른쪽 자식은 을 담당한다 (). 질의 구간이 이 중 하나에 포함된다면 해당 자식 노드로 이동하여 같은 방법을 재귀적으로 적용하면 된다.

3. 양쪽 자식 모두와 겹치는 경우

   이 경우 왼쪽 자식과 오른쪽 자식 각각에 대해 부분 질의를 수행하고, 결과를 합친다. 즉, 의 합은 왼쪽 자식으로, 의 합은 오른쪽 자식으로부터 얻고 둘을 더한다.

이러한 방식으로 합 질의는 재귀적으로 처리되며, 재귀는 현재 노드가 질의 구간과 정확히 일치할 때 종료된다. 이때는 해당 노드에 저장된 미리 계산된 값을 반환하면 된다.

즉, 합 질의는 트리를 필요한 만큼만 순회하여 구간을 나누고, 나뉜 구간들의 합을 미리 저장된 값을 이용해 계산하는 방식이다.

트리 순회는 루트 노드부터 시작한다.

다음 그림은 일 때, 를 계산하는 과정이다. 방문한 노드는 색으로 표시되어 있으며, 초록색 노드는 해당 값을 직접 사용한다. 결과는 이다.

이 알고리즘의 시간 복잡도가 인 이유는 무엇일까? 트리의 각 레벨마다 방문하는 노드는 최대 4개 이하이며, 트리의 높이가 이므로 전체 방문 노드 수는 개이다.

이는 수학적 귀납법으로 증명할 수 있다. 첫 번째 레벨에서는 루트 하나만 방문한다. 임의의 레벨에서 4개 이하의 노드를 방문한다고 가정하면, 다음 레벨에서도 각 노드가 자식 최대 2개만 방문하므로 총 8개를 넘지 않는다. 그러나 연속된 구간 합이라는 특성 때문에 가운데에 있는 완전히 포함된 구간은 더 내려가지 않는다. 따라서 실제로는 좌측 경계와 우측 경계에 해당하는 두 노드만 재귀호출을 한다. 결과적으로 한 레벨에서 최대 4개만 방문하게 된다.

따라서 전체적으로 개의 노드만 방문하며, 시간 복잡도는 이다.

즉, 구간 합 질의는 질의 구간을 몇 개의 작은 구간으로 나누고, 이 구간에 대한 합이 트리에 미리 저장되어 있으므로 시간에 계산할 수 있다.

변경 질의

이제 배열의 특정 원소를 변경하는 경우를 살펴보자. 와 같은 대입 연산을 수행하는 것을 생각해보자. 변경된 배열에 맞게 세그먼트 트리를 갱신해야 한다.

이 연산은 합 질의보다 더 간단하다. 세그먼트 트리의 각 레벨은 배열 전체를 분할하고 있으므로, 어떤 원소 는 각 레벨마다 하나의 구간에만 포함된다. 따라서 갱신이 필요한 노드는 개이다.

이 변경 연산은 재귀적으로 구현할 수 있다. 현재 노드가 포함하는 구간을 확인하고, 가 포함되는 자식 노드로 재귀 호출한 뒤, 자식들의 값을 이용해 현재 노드의 값을 변경하면 된다 (이는 트리 구성 과정과 유사하다).

다음 그림은 동일한 배열에서 으로 변경하는 과정을 나타낸다. 초록색 노드들이 변경된 노드이다.

구현

세그먼트 트리를 구현할 때 가장 먼저 고려해야 할 점은, 이 자료구조를 어떻게 저장할 것인가이다. 물론 Vertex 구조체를 정의하여 각 노드에 대해 구간 정보, 구간 합, 자식 노드 포인터 등을 저장할 수도 있다. 하지만 이렇게 하면 포인터 등 불필요한 정보를 많이 저장하게 되므로 비효율적이다.

이 문제를 해결하기 위해 암시적 자료구조_{implicit data structure}라는 기법을 사용할 수 있다. 이는 트리의 구조를 명시적으로 저장하지 않고, 합 정보만을 배열에 저장하는 방식이다. (이와 비슷한 방식이 이진 힙에도 사용된다.)

예를 들어, 루트 노드의 합은 인덱스 1에, 그 자식 노드들의 합은 인덱스 2와 3에, 그 자식들은 인덱스 4~7에 저장되는 식이다. 1부터 시작하는 인덱싱을 사용할 경우, 인덱스 의 노드의 왼쪽 자식은 , 오른쪽 자식은 에 저장된다. 반대로 부모 노드는 위치에 있다.

이러한 방법을 사용하면 트리 구조를 따로 저장할 필요 없이, 배열 하나만으로 세그먼트 트리를 구성할 수 있어 구현이 매우 간단해진다.

앞서 말했듯이, 최대 개의 노드만 있으면 되므로 크기가 인 배열 하나만 준비하면 충분하다. 실제로는 이보다 적은 노드를 사용할 수도 있으나, 구현의 편의성을 위해 항상 크기로 할당해두는 것이 일반적이다. 이 경우 사용되지 않는 배열 원소들이 일부 존재하더라도 구현상 큰 문제가 되지 않는다.

결국, 세그먼트 트리는 다음과 같이 단순한 배열 하나로 표현할 수 있다:

int n, t[4*MAXN];

void build(int a[], int v, int tl, int tr) {
  if (tl == tr) {
      t[v] = a[tl];
  } else {
    int tm = (tl + tr) / 2;
    build(a, v*2, tl, tm);
    build(a, v*2+1, tm+1, tr);
    t[v] = t[v*2] + t[v*2+1];
  }
}

int sum(int v, int tl, int tr, int l, int r) {
  if (l > r) return 0;
  if (l == tl && r == tr) return t[v];
  int tm = (tl + tr) / 2;
  return sum(v*2, tl, tm, l, min(r, tm))
          + sum(v*2+1, tm+1, tr, max(l, tm+1), r);
}

void update(int v, int tl, int tr, int pos, int new_val) {
  if (tl == tr) {
    t[v] = new_val;
  } else {
    int tm = (tl + tr) / 2;
    if (pos <= tm)
      update(v*2, tl, tm, pos, new_val);
    else
      update(v*2+1, tm+1, tr, pos, new_val);
    t[v] = t[v*2] + t[v*2+1];
  }
}