구간 트리(겹침 질의) 계산기

구간(시작,끝) 여러 개가 있을 때, 주어진 질의 구간과 겹치는 것들을 빠르게 찾기 위한 것입니다. 이진탐색트리에 구간을 시작점 기준으로 넣되, 노드마다 「자기 서브트리 안 모든 구간의 끝점 중 최댓값(max)」을 함께 저장해 둡니다.

탐색 도중 어떤 서브트리를 아예 안 들여다봐도 되는지 판단하는 근거이기 때문입니다. 왼쪽 서브트리의 max가 질의의 시작점보다 작으면, 그 안의 모든 구간이 질의보다 먼저 끝나 겹칠 수 없다는 뜻이라 통째로 건너뜁니다.

트리가 시작점 순으로 정렬되어 있으므로, 지금 노드의 시작점이 이미 질의의 끝점보다 늦으면 오른쪽에 있는(시작점이 더 큰) 구간들은 더더욱 늦게 시작해 겹칠 수 없습니다. 그래서 지금 노드의 시작점 ≤ 질의의 끝점일 때만 오른쪽으로 들어갑니다.

세그먼트 트리는 고정된 배열 위에서 구간 [i,j]의 합·최솟값 같은 것을 답하는, 축이 「배열의 위치」인 자료구조입니다. 구간 트리는 반대로 구간 「집합」 자체가 데이터이고 「이 구간과 겹치는 것이 있는가」를 답합니다 — 캘린더 일정 겹침, 스케줄링 충돌 검사, 지놈 구간 겹침 같은 곳에 씁니다.

전송되지 않습니다. 계산은 모두 브라우저 안에서 이뤄지고 입력값은 이 기기에만 남습니다.