집합이 시간에 따라 변화하는 동안 k 번째로 큰 원소를 효율적으로 찾는 방법?

Question

집합에서 k 번째로 큰 요소를 요청하는 쿼리가 있습니다.

그리고 요소를 추가, 삭제 또는 변경할 수있는 몇 가지 업데이트가 있습니다.

이 작업을 효율적으로 수행하는 방법은 무엇입니까?

미리 감사드립니다. (노드의 서브 트리의 크기를 저장하는 각각의 노드에 대해 변형)

Answer 1

A는 Binary Search Tree 트릭을 수행한다.

찾기 k 번째로 큰 O(log n) 시간이 소요됩니다.

각 추가, 제거 및 업데이트 (제거, 추가)는 각각 < = O(log^2 n) 시간 (또는 아마도 단지 O(log n))이됩니다.

는 데이터가 조회 방법에 따라 (업데이트 작업의 경우) BST에 포인터와 배열이나 해시 맵이 필요할 수 있습니다.

찾기 k 번째로 큰 같은 것을 볼 것이다 : 그것은 left 및 right 모두를 탐구 할 수 없기 때문에

Node findKthLargest(Node node, int k) 
    if (node.left != null) 
    if (k <= node.left.count) 
     return findKthLargest(node.left, k) 
    else 
     k -= node.left.count 
    if (k == 0) 
    return node 
    if (node.right != null) 
    return findKthLargest(node.right, k) 

를, 그것은 단지 O(log n) 시간이 걸립니다 있는지 분명하다.

추가, 제거 및 업데이트가 서브 트리의 적절한 수를 수정해야하지만 트리의 최대 만 높은 것입니다. 균형 이진 검색 트리를 사용하면 이러한 작업 (카운트 수정 없음)은 각각 O(log n) 시간이 걸리고 카운트 수정을 사용하면 O(log n) 단계마다 O(log n) 추가 작업 (트리 위로 이동) 만 수행하므로 분명히 할 수 있습니다. O(log^2 n) 이상 걸릴.