1. 세그먼트-트리(구간 트리)란?


세그먼트-트리(구간 트리)란 말 그대로 세그먼트(구간)를 저장하는 트리 자료구조다.


이 자료구조의 기능은 임의의 포인트를 어떤 세그먼트가 포함하고 있는지 반환해줄 수 있다.


또한 다음과 같은 구조를 갖는다.



1) 완전 이진 트리 (마지막 레벨을 제외하고 모든 노드는 자식을 두 개 갖는다.)


2) 트리의 잎들은 기본 간격들에 대응된다. 따라서 가장 좌단의 잎은 가장 처음의 기본 간격에 해당한다.


3) 내부 노드들은 기본 간격을 합친 간격에 대응된다.

따라서 두 잎을 자식으로 하는 내부 노드는, 두 잎에 해당하는 기본 간격을 합친 간격에 대응된다.



위와 같은 규칙으로 우리는 다음 기능들을 유추해 낼 수 있다.


1) n개의 간격이 있다면, 최대 4n + 1 개의 기본 간격이 있을 수 있다. 기본 간격은 잎에 대응된다.

그래서 이진트리의 잎이 4n + 1개 이므로, 높이는 O(log n)이다. 따라서 사용하는 공간은 O(n * log n)이다.


2) 루트 노드부터 1번, 왼쪽 자식은 2번, 오른쪽 자식은 3번, ... 식으로 번호를 매긴다면 다음이 성립한다.

부모 노드가 k번 이라면 왼쪽 자식은 2 * k 번, 오른쪽 자식은 2 * k + 1 번이다.

또한 n개의 기본 간격이 있다면, 총 노드 수는 2 * n - 1 개다.





2. 세그먼트-트리의 활용분야


세그먼트-트리의 강점은 높이가 log n 이라는 특징에서 비롯된다.


두 가지 질의를 하는 문제가 있다고 하자. (질의는 N번 주어진다.)


1) [from, to] 범위의 정보를 모두 구해라.

2) 기본 간격 A의 정보(a)를 b로 변경해라.


단순히 1번 질의를 O(N)으로 수행할 수도 있다.(1번 질의를 받을 때 마다 매번 구한다)

그러면 총 시간 복잡도는 O(N * N)이 될 것이다.


미리 [from, to]를 구하고 저장해둔다면 1번 질의를 상수시간에 해낼 수 있다.

하지만 2번 질의가 주어지는 순간, 미리 구해둔 정보 중 A와 관련된 모든 정보를 수정해야 한다.

따라서 최악의 경우 시간 복잡도는 동일하다.



하지만 세그먼트 트리는 위와 같은 질의를 높이에 비례해서 해낼 수 있다.


만약 1번 질의로 [1, 6]가 주어졌다고 하자.

루트는 현재 [1, 8]을 알고 있지만, 질의와 관계업는 정보도 갖고 있다. 따라서 왼쪽과 오른쪽 자식에게 세부 정보를 알아내야 한다.


왼쪽 자식(2번 노드)은 [1, 4]를 안다. 이는 질의의 일부분이다.


오른쪽 자식(3번 노드)은 [5, 8]을 안다. 하지만 질의와 겹치지 않는 부분이 있다. 다시 왼쪽, 오른쪽 자식에게 세부 정보를 알아내자.


3번 노드의 왼쪽 자식(6번 노드)은 [5, 6]을 안다. 이는 질의의 일부분이다.

3번 노드의 오른쪽 자식(7번 노드)은 [7, 8]을 안다. 이는 질의와 상관없는 정보다.


따라서 2번 노드와 6번 노드를 합치면 질의에 답할 수 있다.



2번 질의 또한 위와 유사한 과정을 통해 부모 노드들을 갱신시켜가면서 수행된다.


1번 질의와 2번 질의 모두 루트부터 시작된 트리 탐색으로 높이에 비례한 수행시간을 가진다.


따라서 세그먼트-트리의 위와 같은 질의에 대한 수행시간은 O(log n)이다.




3. 문제에 적용


정보 탐색과 갱신은 루트부터 시작된다.


탐색은 노드의 번호와 기타 정보를 통해 아래방향으로 진행된다.


하지만 갱신은 갱신 노드에 도달한 이후 윗방향으로 이루어진다. 따라서 재귀적인 코드가 직관적이다.



3-1) 백준 : 2042 구간 합 구하기 https://www.acmicpc.net/problem/2042


코드 : 


3-2) 백준 : 10868 최소값 https://www.acmicpc.net/problem/10868


코드 : 


+ Recent posts