세크먼트 트리(Segment Tree)

주어진 배열에 대한 구간 쿼리를 빠르게 처리하기 위한 자료구조 주로 구간 합, 최소/최대값 등의 쿼리를 처리하는데 사용합니다.

세그먼트 트리는 이진 트리(Binary Tree)의 형태를 가지며, 각 노드는 해당 구간의 정보를 담습니다. 이때, 구간은 일반적으로 배열의 인덱스를 의미하며, 루트 노드는 전체 구간을 나타냅니다.

세크먼트 트리가 생성되는 과정

1. 주어진 배열을 이진 트리의 리프 노드에 저장한다.
2. 이진 트리의 각 노드에 대해, 해당 노드가 담당하는 구간의 정보를 계산하여 저장한다. 이때, 구간의 정보는 리프 노드의 정보를 합쳐서 계산한다.
3. 쿼리를 처리할 때, 주어진 구간을 세크먼트 트리의 노드들로 분해하고, 해당 노드들의 정보를 합쳐서 구간의 정보를 계산한다.

세그먼트 트리는 구간 쿼리를 O(logN)의 시간 복잡도로 처리할 수 있어 대용량의 데이터에서 구간 쿼리를 빠르게 처리할 수 있는 장점이 있습니다. 그러나 구현이 복잡하고 일부의 경우 다른 자료구조보다 느리게 동작할 수 있습니다.

세그먼트 트리는 이진트리로 구조가 만들어집니다. 배열 [1 -1, 0, 1, 1, -1, 1] 이 있을때 부분 수열의 합을 구하면 다음과 같은 구조를 가지게 됩니다.

/** 1번 */ 
        2
       /  \
     1       1
   /  \     / \
  0    1   0   1
 /\	  /\  /\  /
1 -1 0 1 1 -1 1

만약 쿼리가 2부터 5까지라면 아래와 같은 구조를 가집니다.

/** 2번 */ 
     1
    /  \ 
  -1     2
 / \    / \
-1  0  1   1

1번과 2번의 구간 합이 달라집니다.

예제 문제로 합이 0인 구간합의 가장 긴 구간의 길이를 구하라는 문제를 예시로 들어보겠습니다.
1번에서는 합이 0이 되는 구간은 [1:2]와 [5:6]이 있고 둘다 길이가 같기에 가장 긴 길이는 2입니다.
2번 문제에서는 0이 되는 합이 없기에 0이됩니다.