구간 트리는 저장된 자료들을 적절히 전처리해 그들에 대한 질의들을 빠르게 대답할 수 있게 한다.

흔히 일차원 배열의 특정 구간에 대한 질문을 빠르게 대답하는 데 사용한다. 예를 들어, 구간의 최소치를 구하는 문제이다. A = { 1, 2, 1, 2, 3, 1, 2, 3, 4 }라면 [ 2, 4 ] 구간의 최소치는 1이고, [ 6, 8 ] 구간의 최소치는 2이다.

이를 구현하는 가장 간단한 알고리즘은 순회하여 O(n)의 시간이 걸린다.

이를 전처리해서 구간 트리를 생성하면 연산을 빠르게 구현할 수 있다.

구간 트리의 기본적인 아이디어는 주어진 배열의 구간들을 표현하는 이진 트리를 만드는 것이다.

이때, 구간 트리의 루트는 항상 배열의 전체 구간 [0, n-1]을 표현하며, 한 트리의 왼쪽 자식과 오른쪽 자식은 각각 해당 구간의 왼쪽 반과 오른쪽 반을 표현한다. 즉, 리프 노드는 길이가 1인 구간일 것이다.

이때 구간 트리는 노드마다 해당 구간에 대한 계산 결과를 저장해 둔다. 위 예시 문제의 경우는 구간의 최소치를 각 노드에 저장한다.

어떤 구간 [ i, j ]가 주어지면 이를 노드로 만들어진 구간들의 합집합으로 표현할 수 있다.

예를 들어 [ 6, 12 ] 구간은 [ 6, 7 ], [ 8, 11 ], [ 12, 12 ]의 합집합으로 표현 가능하다. 이 셋 중의 최소치가 우리가 원하는 답이 된다.

어떤 구간이 주어지던 간에 고려해야 하는 구간의 수는 O(lgn)이다.

예시 문제