Segment Tree란?
Segment Tree는 이진 트리 형식을 따르는 자료구조 중 하나이다. 다양한 구간에 대한 특정 연산들(max,min,sum,…)을 쉽고 효율적으로 처리하기 위해서 만들어졌다. 참 직관적으로 이해가 잘 간다. 그렇지 않은가? 전혀 그렇지 않다. 이게 무슨 소린가? 이게 이해가 되는가? 난 전혀 안되는 것 같다. 이진 트리는 알겠지만 그 뒤에 나오는 구간이 정확히 뭘 뜻하는지 연산들이라 함은 무슨 뜻인지 글만 봐서는 한계가 있다. 그렇기에 예시를 통해서 좀 더 자세하게 알아보도록 하자.
예를 들어 총 5개의 데이터가 길이 5의 배열에 저장되어 다음과 같은 형태라고 해보자.
이때 첫번째 쿼리로 0 번부터 2 번까지의 값 중 최소값을 찾아보면 아래와 같다.
두번째 쿼리로 1번부터 2번까지의 값 중 최소값은 아래와 같다.
위의 예시처럼 하나의 배열 안에서도 다양한 구간에 대한 정보를 원하는 다양한 쿼리가 올 수도 있다. 이렇게 다양한 구간에 대해서 예시에서는 최소값만을 구하였지만 최대값, 합 등의 다양한 연산을 효율적으로 할 수 있도록 만들어진 트리형식의 자료구조가 Segment Tree이다. Segment Tree를 만드는 방법과 더 자세한 동작 방법은 아래에서 다루도록 하겠다.
마지막 쿼리로 2번부터 4번까지의 값 중 최소값은 아래와 같다.
위의 예시처럼 하나의 배열 안에서도 다양한 구간에 대한 정보를 원하는 다양한 쿼리가 올 수도 있다. 이렇게 다양한 구간에 대해서 예시에서는 최소값만을 구하였지만 최대값, 합 등의 다양한 연산을 효율적으로 할 수 있도록 만들어진 트리형식의 자료구조가 Segment Tree이다. Segment Tree를 만드는 방법과 더 자세한 동작 방법은 아래에서 다루도록 하겠다.
왜 사용하는가?
Segment tree는 위에서 언급이 되었듯, 구간에 대해서 연산 및 처리가 굉장히 효율적으로 이루어지기 때문에 사용된다. Segment Tree 자료구조를 사용하지 않고 처리를 하는 경우를 생각해보며 관련 처리가 얼마나 비효율적인지 알아보자. 위에서 사용된 예시를 이용하겠다.
Brute-Force 알고리즘
먼저 첫번째 쿼리 즉, 0번~2번 구간에서 최소값을 찾을 때 구간 안의 모든 수 즉 1번, 2번, 3번의 수들을 비교하여 최소값을 찾는다. 다음으로 두번째 쿼리 즉, 1번~2번 구간에서 최소값을 찾을 때 또한 1번과 2번 값을 비교하여 최소값을 찾는다. 마지막 쿼리 또한 2번부터 4번까지 모든 값을 비교 해보고 최소값을 찾는다.
자 어떤가? 직관적이고 충분히 효율적이고 쉽지 않는가? 각 쿼리에 대해서 구간의 길이가 m이라 하면 O(*m)*이면 알 수 있다! 그런데 왜 굳이 복잡한 다른 자료구조를 알아야 하는가? 언뜻 보기에는 쉬워 보일 수도 있고 좋아보일 수 있지만, 쿼리의 수가 늘어나 1만개의 쿼리가 올 경우 또 구간의 길이가 최대 5가 아닌 1억인 경우, 모든 업무를 처리하는데 시간복잡도는 O( 1만 X 1억)이 되어 많은 시간이 필요하게 되고 이는 데이터의 수가 늘어나면 늘어날 수록 기하 급수적으로 늘어나게 된다.
Dynamic Programming(DP)을 사용할 경우
속도적인 측면에서의 문제를 해결하기위해 DP를 사용해보자. 예시에서는 최대값을 찾는 경우를 생각해보겠다. 방법은 다음과 같다.
- 배열의 크기가 n이라 할 때, 0번째 수부터 1번째 수까지의 최대값을 구하여 새로운 2차원 배열(이를 table이라 부르겠다) 0번째 행 1번째 열에 저장한다.
- table[0][1]과 2번째 수를 비교하여 최대 값을 table[0][2]에 저장한다.
- 2번과 같은 방법을 반복하여 table[0]의 모든 열에 값을 추가한다.
- 0번째 수부터가 아닌 1번째 수부터 시작하여 1~3번을 반복하여 table[1]에 해당하는 모든 열을 추가한다.
- 마지막 n-1 번째 수까지 반복하여 table을 채운다.
이를 위의 예시에 적용해보겠다. 그러면 table은 다음과 같다.
이렇게 table이 주어지면 첫번째 쿼리는 0번 행에 2번 열을 확인하면 바로 최소값이 2임을 알 수 있다. 또 두번째 쿼리의 경우 1번 행에 2번 열을 보면 해당 최소값을 알 수 있고 마지막으로 3번째 쿼리는 2번행의 4열을 보면 1임을 알 수 있다.
앞서의 방식보다 쿼리에 대한 처리 속도가 확연하게 빨라진 것을 알 수 있다. 배열의 크기를 n, 쿼리의 숫자를 m이라 할 때, 위의 방식을 사용하는데 걸리는 총 시간은 table 배열을 만드는데 O(*n * n)*의 시간이 걸리고 그 후에 쿼리의 수 m이 아무리 증가하더라도 값을 찾아오는데 드는 시간은 O(1)이다. Brute-Force 방식보다 빨라보이지만 사실 DP 방식에는 두가지의 문제가 존재한다. 첫번째는 m보다 n의 수가 클 경우 Brute-Force 방법보다 비효율적이다. 두번째는 추가적인 메모리가 n * n만큼 추가적으로 필요하여 메모리에 대한 부담도 크다.
이렇듯 쿼리가 늘어나고 총 배열의 크기가 커지면 기존의 방법들의 비효율성은 기하급수적으로 늘어나기 때문에 보다 효율적이고 합리적인 방법이 필요했고 이를 해결해준 것이 Segment Tree이다. 자 그러면 이제 이 글의 이유이자 목표이자 빛과 소금인 Segment Tree를 자세하게 알아보자.
Segment Tree 만들기
최대 값을 찾는 쿼리에 대한 Segment Tree를 만드는 방법은 다음과 같다.
- 배열에 저장된 값들은 모두 트리의 리프 노드가 된다.
2. 각 노드의 부모 노드는 두 자식 노드 중 가장 더 작은 수가 된다.
3. 2번을 반복하여 루트 트리까지 값을 채워넣는다.
이러면 위의 예시 배열에 대해서 최소값을 찾는 Segment Tree가 만들어졌다! 갑자기 다른 내용이지만 피피티로 저런거 만드는거 진짜 되게 힘들다.
자, 그럼 이제 쿼리는 어떻게 처리를 하는지 알아보자. 아래의 세가지 룰을 고려해서 진행하면 원하는 구간에서 특정 연산의 답을 빠르게 얻을 수 있다.
먼저 세가지 룰은 다음과 같다. 먼저 시작 노드는 루트 노드이다.
- 쿼리의 구간이 노드의 구간을 일부 포함되면 자식 노드로 이동한다.
- 쿼리의 구간이 노드의 구간을 포함하거나 같으면 노드의 값을 부모 노드로 반환한다.
- 쿼리의 구간과 노드의 구간이 서로 포함 관계가 없으면 부모 노드로 아무것도 반환하지 않는다.
여기서 노드의 구간이란 특정 노드가 포함한 정보들의 구간이다. 예를 들어 루트 노드의 경우 모든 리프 노드에 대한 정보가 담겨있음으로 위의 예시에서 루트 노드의 구간은 0~4이다. 바로 좌측 자식 노드 2는 0번과 1번의 정보를 가지고 있으므로 구간은 0~1이고 오른쪽 자식 노드는 2~4번의 정보를 가지고 있으므로 오른쪽 자식 노드의 구간은 2~4이다.
각 리프 노드들의 구간은 자기 자신 하나만을 가지고 있다. 더 확실한 이해를 위해서 몇 가지 쿼리가 어떻게 찾아지는지 알아보자.
쿼리 1: 0번째 ~ 3번째 쿼리에서 최소값 찾기
- 먼저 루트 노드에서 시작한다. 루트 노드의 구간은 0~4이고 쿼리의 구간은 0~3이므로 1번 룰에 해당된다. 그러므로 양쪽 자식 노드로 이동한다.
- 먼저 왼쪽 자식 노드를 살펴보자. 왼쪽 자식 노드의 구간은 0~1이고 쿼리의 구간은 0~3이다. 2번 룰에 해당하여 노드의 값인 2를 반환한다.
- 다음으로 오른쪽 자식 노드를 살펴보자. 오른쪽 자식 노드의 구간은 2~4이고 쿼리의 구간은 0~3이다. 그러므로 1번 룰에 해당되어 다시 양쪽 자식 노드를 확인한다.
-왼쪽 자식 노드의 구간은 2~3이므로 쿼리의 구간에 포함되어 값을 1이라는 값을 반환한다.
-오른쪽 자식 노드의 구간은 4이므로 쿼리의 구간 관계가 없어 부모 노드에 아무것도 반환하지 않는다.
4. 2번에서 왼쪽 자식 노드로 부터 받아온 2와 3번에서 오른쪽 자식 노드로 부터 받아온 1을 비교하여 더 작은 수인 1을 반환한다. 즉 0~3번 구간 안에서 가장 작은 값은 1이다.
이렇게 간단하게 최소값을 찾을 수 있다!
Segment Tree Time Complexity
Segment Tree 생성:
O(n)
생성하는데 있어서는 맨 아래 leaf node에 값들을 지정하고 그 위에 그래프를 만들기 때문에 *n + log(n)*의 시간이 걸린다.
Query 탐색:
O(log(n))
Segment Tree도 이진 탐색 트리와 같은 구조이기 때문에 탐색에 있어서 log(n)만큼의 시간만이 걸린다. 바로 이 성질 때문에 생성하는 부분에서 n의 시간이 걸리더라도 Query 탐색이 naive한 방법에 보다 빠르다. 그렇기에 query의 수가 많거나 늘어날 경우 Segment Tree가 훨씬 효율적이다.
Credit: 알고리머 김태균 인턴
