Order Statistics Tree (OST): rank/select 지원 BST

Order Statistics Tree, OST, 순위 통계 트리

정의

Order Statistics Tree 는 각 노드에 서브트리 크기 를 추가로 저장한 균형 BST 입니다. 두 가지 새 연산을 O(log N) 에 지원합니다.

• rank(x): x 보다 작은 원소 수
• select(k): k 번째 원소 (0-indexed)

구조

struct Node {
    int key, size;
    Node *l, *r;
};

int sz(Node* n) { return n ? n->size : 0; }

Node* select(Node* r, int k) {
    if (!r) return nullptr;
    int lsz = sz(r->l);
    if (k == lsz) return r;
    if (k < lsz) return select(r->l, k);
    return select(r->r, k - lsz - 1);
}

int rank(Node* r, int key) {
    if (!r) return 0;
    if (key <= r->key) return rank(r->l, key);
    return sz(r->l) + 1 + rank(r->r, key);
}

일반 BST 삽입/삭제 시 size 를 함께 갱신합니다.

실전 구현

• C++ policy tree (GNU): __gnu_pbds::tree with tree_order_statistics_node_update
• Rust: BTreeSet 은 미지원, 별도 구현 필요
• Python: SortedList (sortedcontainers) 가 유사

참고

• BST
• Treap
• Fenwick Tree (좌표 압축 후 rank/select 대체)