누적 간격의 데이터 구조

Question

너비가 정수 인 항목 목록이 있는데, 왼쪽에서 오른쪽으로 간격을 쌓아서 해석 할 수 있습니다. 항목의 오프셋을 나타내는 아래

숫자는 예를 들어, 상품의 폭을 각각 5,2,2,3,2 및도 4 A, B, C, D, E 및 F하고 있다고 가정 리스트의 시작

I 효율적으로 이상적 O 이하 (N)에 그 작업을 지원하는 데이터 구조를 찾고 있어요 :

• 가 주어진 위치에서 항목을 찾을 수 있습니다. 예를 들어 위치 11의 항목은 9부터 12까지이므로 D이고 위치 14의 항목은 거기서 시작된 이후 F입니다.
• 기존 항목 두 개 사이에 항목을 삽입하거나 기존 항목을 제거하십시오. 이것은 후속 항목의 위치를 ​​이동시켜야합니다. 예를 들어 항목 E를 제거하면 항목 F가 왼쪽에서 두 자리로 이동하여 12에서 16으로 확장됩니다.

건너 뛰기 목록과 비슷한 항목을 사용하여 각 수준이 너비를 저장하고 있다고 생각했습니다. 아래의 레벨을 포함하지만, 나는 어떤 성능 특성을 얻을 수 있는지에 대해 너무 확신하지 못한다.

제안 사항?

Answer 1

rope의 변형은 어때요?

잎에 줄이있는 대신 간격이 있습니다.

특정 위치를 포함하는 간격을 찾는 것은 O (log n)입니다 (색인 대신 색인을 반환하도록 로프의 색인 알고리즘을 수정하면됩니다).

어디에서나 항목을 삽입하면 O (log n)이됩니다 (한 번 분할하고 두 번 연결하면 모두 O (log n)이됩니다). 당신은 몇 가지 불운으로 실행하면 자연의 확률이고, O (n)이 최악의 경우가있는 skiplist, 달리

, 그 작업이 될 것이다 O (로그 n) 보장 (당신이 O를 ​​사용하는 가정() 로그 n 밸런싱 - 연결).