[1] Segment Tree

Segment Tree 는 다양한 유형의 문제를 빠르게 해결해주는 자료구조이다. 

구간에 대한 정보를 구하는 경우, 단순히 정렬한 후 Prefix Sum 을 이용해서 구간합을 빠르게 구할 수 있지만

만약 개별 쿼리 도중 배열에서 특정 요소의 값이 변경되야 하는 경우엔 매번 다시 정렬을 해야 되어 비효율적이다. 

 

이러한 경우, 구간에 대한 정보를 담는 Tree를 구성할 수 있는데, 이를 세그먼트 트리라고 한다. 

세그먼트 트리는 기본적으로 Complete Binary Tree이고, 모든 Element에 대한 정보가 트리의 Leaf Node에 포함된다.

그리고 그 위 node들은, 자식 node를 포함하는 구간에 대한 정보를 담는 것이다. 

 

간단하게, 세그멘트 트리를 이용해서 구간합을 구하는 코드의 예시를 보자. 

여기서는 배열을 이용하여 segtree를 구현하였다. 

 

ll input_data[1000001];
ll segtree[2100000]; // 들어오는 입력의 갯수가 항상 트리의 밑에 다 깔릴 수 있게 구성해야 (그냥 2배가 아니라 2^n 형식으로)

void init(int node, int S, int E)
{
  if (S == E)
  {
    segtree[node] = input_data[S];
    return;
  }

  init(node * 2, S, (S + E) / 2);
  init(node * 2 + 1, (S + E) / 2 + 1, E);
  segtree[node] = segtree[node * 2] + segtree[node * 2 + 1];
}

세그멘트를 초기화하는 작업이다. 재귀적으로 동작하되, Leaf에 도달하면 저장한 값을 지정해주고, 그렇지 않으면 재귀적으로 더 탐색하고 돌아와서 자식 노드의 값을 합친 결과를 저장한다. 시간복잡도는 O(N)이다. 

 

void update(int node, int S, int E, int k, ll x)
{
  if (S == E)
  {
    segtree[node] = x;
    return;
  }

  if ((S + E) / 2 >= k)
    update(node * 2, S, (S + E) / 2, k, x);
  else
    update(node * 2 + 1, (S + E) / 2 + 1, E, k, x);

  segtree[node] = segtree[node * 2] + segtree[node * 2 + 1];
}

세그멘트를 업데이트하는 작업이다. 구간 S E에 대해 k의 위치에 x를 넣는 작업인데

이분탐색 후 마지막 node로부터 그 부모노드를 하나하나씩 업데이트 하는 과정으로 O(logN) 이다. 

 

ll find(int node, int S, int E, int i, int j)
{
  if (j < S || i > E)
    return 0LL;

  if (i <= S && E <= j)
    return segtree[node];

  return find(node * 2, S, (S + E) / 2, i, j) + find(node * 2 + 1, (S + E) / 2 + 1, E, i, j);
}

세그멘트에서 구간의 합을 구하는 작업이다. 이 개념이 가장 중요하다.

구간 S E에 대해 i j 구간의 합을 구하는 것이 목표인데

 

내가 찾으려는 구간 (i j)이 바라보는 구간(S E)를 포함하면 그걸 통채로 리턴하고

아예 포함이 안되면 0을 리턴하고

걸쳐있는 경우엔 다시 양쪽을 분할해서 재귀적으로 find를 수행한다.

결국 "안 걸쳐져있는" 상태 까지 쪼갠 결과들을 모두 합쳐서 찾아내는 것이다. 

 

node에 담겨있는 값에 따라 구간의 합, 최소값, 최대값 등 다양한 것들을 빠르게 찾을 수 있다. 

그 이상의 예시들은 더 공부를 하고 문제를 풀어봐야 알 수 있을 것 같다. 

 

알고리즘을 가르쳐주는 사부님 덕분에 빠르게 이해할 수 있었다 매우 기쁘다. 

왜 학원을 다니는지.. 조금은 알 것 같기도 하다. 사부님을 향해 절을 하며 글을 마친다.