요약
- 일차원 배열의 특정 구간에 대한 질의(최소값, 합 등)를 O(log n)에 처리하는 트리 자료구조
본문
- 트리는 단순히 저장 용도로만 사용되지는 않음
- 구간 트리는 저장된 자료들을 적절히 전처리해 질의를 빠르게 대답 할 수 있도록 함
- 특히 일차원 배열의 특정 구간에 대한 질문을 빠르게 대답하는데 사용됨
- 어떤 배열 A의 부분 구간의 최소치를 구하는 연산을 여러번 하고 싶다고 가정
- A = [1,2,1,23,1,2,3,4]
- 가장 간단한 알고리즘은 O(n)의 시간이 걸림
- 구현 아이디어
- 주어진 배열의 구간을 표현하는 이진 트리를 만드는 것
- 구간 트리의 루트는 항상 배열의 전체 구간 [0, n-1]을 표현
- 구간 트리는 각 노드마다 해당 구간에 대한 계산 결과를 저장해둠
이런 전처리 과정을 통해, 어떤 구간 i,j가 주어지더라도 이 구간을 구간 트리의 노드의 합집합으로 표현 가능함
표현
-
특정구간의 최소값을 찾는 문제로 풀어보자
-
RMQ(Range Minimum Query) 문제
-
구간 트리는 꽉 찬 이진 트리
-
꽉찬 이진 트리의 경우, 포인터로 연결된 객체보다 배열로 표현하는게 메모리를 절약할 수 있는 방법
-
루트가 i 일때, 2i 오른쪽 노드, 2i+1이 왼쪽 노드
-
배열의 길이
- n이 2의 거듭 제곱인 경우, 2n
- 아닌 경우, 가장 가까운 2의 거듭 제곱으로 올린후 2를 곱해야함
- n=6인 경우, 8 , 8* 2= 16
- 안전하게 계산하려면 n에 4를 곱하면 됨
-
초기화 시간 복잡도: O(n)
- 노드의 수에 의해 결정됨
-
질의 처리
- 원하는 구간에 완전히 포함되거나 겹치지 않는 경우에는 탐색을 종료하기 때문에,
-
구간 트리의 갱신
-
각 구간의 연산 결과를 저장시켜 놓은 자료 구조
-
Top-> Bottom
-
Bottom -> Top