가장 작은 k 개의 숫자와 쿼리 합계를 더하는 데이터 구조가 있습니까?

Question

아래의 2 가지 작업을 지원하는 데이터 구조가 있습니까?

1. 컬렉션

2. 쿼리 K가 쿼리를 부여하며 컬렉션의 크기만큼 큰 수 있습니다 컬렉션에서 가장 작은 케이 숫자의 합계에 정수를 추가합니다.

두 연산 모두 O (logn)보다 크지 않은 시간 복잡도가 있어야합니다. 여기서 n은 컬렉션 크기입니다.

Answer 1

증강 된 BST가 트릭을해야한다고 생각합니다. 즐겨 찾는 균형 이진 검색 트리 (빨강/검정, AVL, 희생양 등)를 가져 와서 각 노드에 두 개의 추가 필드를 저장하게하십시오 :

1. 노드의 왼쪽 하위 트리에 몇 개의 노드가 들어 있습니까?
2. 노드의 왼쪽 하위 트리에있는 모든 값의 합계입니다.

이러한 속성은 O (log n) 시간마다 삽입 및 삭제를 수행 할 때 유지 관리 할 수 ​​있습니다. (이 방법을 알지 못했다면 CLRS에서 자세한 내용을 확인하십시오. 멋진 구성입니다!)

이 작업을 완료하면 정규 시간에 O (log n) 시간 내에 삽입 작업을 수행 할 수 있습니다. 삽입 다음에 모든 O (log n) 시간이 걸린 모든 캐시 된 값을 수정합니다.

k 개의 가장 작은 값의 합을 얻으려면 트리를 반복적으로 볼 수 있습니다. 특히, 루트 노드를보십시오. 그런 다음 : 루트 노드가 정확히 K가있는 경우

는

1. - 자사의 왼쪽 하위 트리에있는 한 요소를 k 개의 작은 요소의 합은 (그 왼쪽에있는 K-1 요소의) 루트의 캐시 된 금액을 반환하여 찾을 수 있습니다 루트의 값을 더한 값.
2. 루트가 왼쪽 하위 트리에 k 개 이상의 요소가있는 경우 재귀 적으로 왼쪽 하위 트리로 내려 가서 k 개의 가장 작은 요소의 합계를 반환합니다.
3. 루트가 왼쪽 하위 트리에 m < 개의 요소가있는 경우 루트의 캐시 된 합계와 루트의 오른쪽 하위 트리에있는 k - m - 1 가장 작은 요소의 (재귀 적) 합계를 더합니다.

이렇게하면 단일 루트 - 리프 연결이 트리 아래로 내려가 O (log n) 시간이 걸립니다.

Answer 2

당신은 당신은 또한 노드의 합을 저장,이 하위 트리의 노드의 수를 저장하는 것 외에도, 각 노드에서 index statistics tree (AKA ranked tree), 어디의 변화와 함께 할 수 있습니다. 노드 당 계산할 수 있습니다. self.subtree_sum = left.subtree_sum + right.subtree_sum + self.value.

그러면 k 번째까지의 모든 요소의 합계는 통계 트리에서 k 번째 요소를 찾는 것과 동일하게 수행되지만, 노드 수 이외의 값도 합계 할 수 있습니다.