A set of intervals on the real line is proper when no interval contains another interval and it is independent when the intervals are pairwise disjoint. We provide a data structure to maintain a proper set of intervals under insertions, deletions and queries for the size of the largest independent subset in O(log n) time per operation, where n is the number of intervals. For some restricted cases we can also report a largest independent subset in O(k + log n) time, where k is the size of the output. The best previous results for this scenario performed updates in O(log 2 n) amortized time.
이 논문에서 우리는 서로 포함하지 않는 실선 구간들의 집합의 최대 독립 부분집합을 유지하고 구간의 추가와 삭제 연산을 지원하는 데이터 구조를 제시한다. 이 데이터 구조는 총 구간의 개수가 n개일때 구간 추가와 삭제 연산, 그리고 최대 독립 부분집합의 크기를 구하는 연산을 각 O(log n) 시간에 지원한다.
우리는 이전 연구 결과와 비슷하게 각 구간의 오른쪽으로의 탐욕 해법을 인코딩한 트리들을 유지한다. 우리는 이전 연구 결과에 변화를 주어 각 노드의 자식 노드들을 오른쪽 끝점 순서대로 정렬하고, 이 임베드된 숲을 오일러 경로 표현법으로 저장한다. 따라서 구간의 추가와 삭제 연산은 오일러 경로 표현법을 구현하는 균형 이진 트리의 join과 split연산 상수 개수로 처리된다.
