큰 트리 구조의 'offset'필드를 업데이트하는 효율적인 방법

Question

큰 (> 백만 개 요소) 트리가 있고 각 요소에 외부 필드를 참조하는 '오프셋'필드가 있습니다. 둘 다해야합니다 :

1. 임의의 위치에 새 요소를 삽입하십시오. 각 삽입은 이후 요소의 'offset'필드를 어느 정도 증가시킵니다.
2. 요소의 오프셋 값을 빠르게 얻습니다.

2가 필요하지 않은 경우 이전 오프셋을 기준으로 오프셋을 저장하면 삽입 후 모든 항목을 업데이트 할 필요가 없습니다. 하지만 그것은 한 요소의 절대 값을 계산하기 위해 모든 이전 오프셋을 더해야 할 필요가 있음을 의미합니다.

이런 종류의 일을하는 표준 방법이 있습니까? 예를 들어 모든 n 번째 요소가 절대 오프셋을 가지며 다른 요소의 오프셋은 이전의 절대 값과 관련되어 있으므로 두 경우 모두 소량의 탐색을 수행해야한다는 것을 의미하는 절충안을 생각해 보았습니다.

Answer 1

몇 가지 접근법은 절대 오프셋을 저장하는 일부 요소를 사용한다는 아이디어를 기반으로합니다. 그들 (나는 그것이 tiered vector의 버전이라고 생각)의

하나는 다음 sqrt(N)에서 등등 2 * sqrt(N)와의 요소를, 최초의 연속 sqrt(N) 요소 오프셋의 변화를 저장하는 것입니다. 그런 다음 주어진 요소에 대한 오프셋을 찾으려면 이전 요소의 연속적인 합계 (모두 sqrt(N) + 1, 이후 (sqrt(N)^2) = N)를 합계 한 다음 마지막 전체 그룹 뒤의 요소를 추가해야합니다. 요소를 추가하면 삽입 및 검색 시간이 O(sqrt(N))이됩니다.

또한 다음 단계로이 방법을, 그리고의 합계를 저장할 수 있습니다 :

• 전체 구간
• 간격
• 1의 제 1 및 제 2 반 ... 4

이 방법을 사용하면 간격 또는 세그먼트 트리와 유사하지만 정확히 같은 것은 아닌 데이터 구조를 얻을 수 있습니다. 간단한 배열을 사용하여 완전한 이진 트리로 구현할 수 있습니다. 두 작업 모두에 대해 O(log N)의 복잡성을 제공합니다.

이 아이디어를 약간 개선하면 Binary Indexed Trees이됩니다. 이는 동일한 복잡성을 가지지 만 약 절반의 공간을 사용합니다.