구간 트리란

image.png

어떤 배열이 주어졌을 때 그 배열의 특정 구간의 최소값을 알고싶다고 하자. 만약 배열 그 자체로 접근하고자 하면 구간에 속한 원소들을 일일이 확인해야 하기 때문에 n의 시간복잡도를 필요로 한다. 이를 효율적으로 수행하기 위한 구조가 구간 트리이다. 구간 트리는 특정 구간의 최소값을 컨테이너에 담고 있는데 담고 있는 구조가 이진 트리의 형식을 취하고 있다.

구간 트리의 구현

주어진 배열에 대한 정해진 구간의 최소값을 구하기 위해 구간을 절반씩 나눠가면서 구간의 크기가 1이 될 때까지 재귀적으로 최소값을 구하고 그 값을 새로운 배열에 저장한다. 이 때 새로운 배열의 크기는 원래 배열의 두 배를 조금 넘는게 가장 큰 경우이다. 보통 4배로 여유롭게 설정한다.구간의 크기가 1일 때는 그 자체가 구간의 최소값이므로 그 값을 반환한다. 반환하면서 재귀적으로 나뉘어진 옆의 구간과 합쳐지는데 이 때 더작은 값이 상위 레벨로 반환되는 것이다. 이렇게 완성된 구간트리는 인덱스로 표현되는데, 힙과 같이 자식 노드는 부모노드2와 부모노드2+1 인덱스에 존재한다.
구간 트리는 절반씩 분할해 가면서 병합하는 과정을 거치기 때문에 결과적으로 구간 트리의 높이인 logn의 시간 복잡도를 갖는다.

구간 트리의 질의

만들어진 구간 트리를 바탕으로 특정 구간의 최소값을 구할 수 있다. 이 과정도 재귀적으로 반복된다. 구하고자 하는 구간은 원 배열의 전체 크기보다 작거나 같을 것이다. 전체 구간부터 구간을 절반씩 나눠가면서 구하고자 하는 구간과 절반씩 나뉜 구간을 비교해 가면서 재귀적으로 반복한다. 만약 구하고자 하는 구간이 재귀 호출 되는 구간을 포함한다면, 재귀 호출 되는 구간의 최소 값을 그대로 리턴한다. 만약 두 구간이 겹치는 부분이 없는 경우 반환 값이 무시 되도록 큰 값을 리턴한다. 만약 재귀호출된 구간이 구하고자 하는 구간을 포함할 경우 재귀호출 되는 구간을 절반으로 나누어 다시 재귀호출한다.
이 과정을 반복하면 결국 구하고자 하는 구간은 재귀 호출 한번에 둘 중 한 쪽은 겹치는 구간이 없거나 구하고자 하는 구간에 포함되므로 logn번만 반복함으로서 원하는 구간의 최소값을 구할 수 있다.

구간 트리의 갱신