Order Statistics Tree

Pada Chapter sebelumnya kita memakai PBDS ordered set untuk akses by-index pada set tanpa duplikat. Banyak persoalan nyata memerlukan multiset dengan elemen berulang (misalnya nilai siswa dengan banyak nilai sama) sembari tetap mendukung query k-th smallest dan rank. Order Statistics Tree adalah ekstensi yang mendukung duplikat lewat trik composite key, dan membungkusnya dalam API yang nyaman: kth_smallest, kth_largest, rank_of, count_in_range, median. Implementasi ini dibangun di atas PBDS tree<pair<key, unique_id>, ...> dengan comparator lexicographic. Pada Chapter ini kita menyajikan kelas OrderStatisticsTree siap pakai dengan multiset support dan beberapa operasi statistik yang sering dibutuhkan di kompetisi.

Aturan: Multiset dengan Order Statistics #

Tantangan: PBDS tree tidak mendukung duplikat langsung (sama seperti std::set). Untuk mendukung multiset:

Gunakan composite key (value, unique_id) dengan comparator less<pair<int,int>>.
unique_id monoton naik per insert (counter internal).
Karena unique_id unik, setiap insert menambah satu entry. Dua insert dengan value sama tetap terpisah sebagai (v, id1) dan (v, id2).
Query count_less_than(v) = order_of_key({v, INT_MIN}) — jumlah elemen yang (value, id) < (v, INT_MIN) = jumlah elemen dengan value < v.
Query count_in_range(lo, hi) = count_less_than(hi+1) - count_less_than(lo).
kth_smallest(k) = find_by_order(k-1)->first (ambil value-nya saja, abaikan id).

Mekanisme: Composite Key dan Lexicographic Comparator #

Komparator default less<pair<int,int>> membandingkan lexicographically: bandingkan first dulu, bila sama bandingkan second. Ini persis yang kita butuhkan:

(5, 3) < (5, 7) karena first sama dan second lebih kecil.
(3, 100) < (5, 0) karena first lebih kecil (second tidak dilihat).

Jadi insert (5, 1), (5, 2), (3, 3) menghasilkan sorted order: (3,3), (5,1), (5,2). Elemen-elemen dengan value sama dikelompokkan berdekatan sesuai urutan insert.

Untuk query count “elemen value < v”: order_of_key((v, INT_MIN)) memberi posisi pertama yang (value, id) >= (v, INT_MIN). Karena INT_MIN adalah id terkecil mungkin, tidak ada id aktual yang lebih kecil — sehingga hasilnya = jumlah elemen dengan value < v. Tepat.

flowchart TD A["insert(5, id=0)"] --> B["tree: (5,0)"] B --> C["insert(5, id=1)"] C --> D["tree: (5,0), (5,1)"] D --> E["insert(3, id=2)"] E --> F["tree sorted: (3,2), (5,0), (5,1)"] F --> G["order_of_key((5, INT_MIN)) = 1<br/>(hanya (3,2) yang kurang dari)"]

Implementasi OrderStatisticsTree Multiset #

cpp
#include <iostream>
#include <vector>
#include <climits>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef tree<
    pair<int, int>,
    null_type,
    less<pair<int, int>>,
    rb_tree_tag,
    tree_order_statistics_node_update
> ost;

class OrderStatisticsTree {
public:
    void insert(int val) {
        tree.insert({val, counter_++});
    }
    void erase_one(int val) {
        auto it = tree.lower_bound(make_pair(val, INT_MIN));
        if (it != tree.end() && it->first == val) {
            tree.erase(it);
        }
    }
    int kth_smallest(int k) const {
        auto it = tree.find_by_order(k - 1);
        return it == tree.end() ? -1 : it->first;
    }
    int kth_largest(int k) const {
        int idx = (int)tree.size() - k;
        auto it = tree.find_by_order(idx);
        return it == tree.end() ? -1 : it->first;
    }
    int rank_of(int val) const {
        return (int)tree.order_of_key(make_pair(val, INT_MIN)) + 1;
    }
    int count_less_than(int val) const {
        return (int)tree.order_of_key(make_pair(val, INT_MIN));
    }
    int count_in_range(int lo, int hi) const {
        return (int)tree.order_of_key(make_pair(hi + 1, INT_MIN))
             - (int)tree.order_of_key(make_pair(lo, INT_MIN));
    }
    size_t size() const { return tree.size(); }
private:
    ost tree;
    int counter_ = 0;
};

int main() {
    OrderStatisticsTree t;
    int vals[] = {5, 2, 8, 1, 9, 3, 7, 4, 6, 5};  // 5 muncul dua kali
    for (int v : vals) t.insert(v);

    cout << "Size: " << t.size() << '\n';
    cout << "\nK-th smallest (1-indexed):\n";
    for (int k = 1; k <= (int)t.size(); ++k) {
        cout << "  " << k << "-th smallest = " << t.kth_smallest(k) << '\n';
    }

    cout << "\nK-th largest (1-indexed):\n";
    cout << "  1st largest = " << t.kth_largest(1) << '\n';
    cout << "  3rd largest = " << t.kth_largest(3) << '\n';

    cout << "\nRank of (1-indexed):\n";
    cout << "  rank of 5 = " << t.rank_of(5) << '\n';
    cout << "  rank of 1 = " << t.rank_of(1) << '\n';
    cout << "  rank of 9 = " << t.rank_of(9) << '\n';
    cout << "  rank of 6 = " << t.rank_of(6) << '\n';

    cout << "\nCount in range:\n";
    cout << "  count < 5 = " << t.count_less_than(5) << '\n';
    cout << "  count in [3, 7] = " << t.count_in_range(3, 7) << '\n';
    cout << "  count in [1, 10] = " << t.count_in_range(1, 10) << '\n';

    cout << "\nMedian (size=" << t.size() << "):\n";
    int sz = t.size();
    if (sz % 2 == 1) {
        cout << "  median = " << t.kth_smallest(sz / 2 + 1) << '\n';
    } else {
        int a = t.kth_smallest(sz / 2);
        int b = t.kth_smallest(sz / 2 + 1);
        cout << "  median (lower) = " << a << ", (upper) = " << b << '\n';
    }
    return 0;
}

Output yang Dihasilkan:

text
Size: 10

K-th smallest (1-indexed):
  1-th smallest = 1
  2-th smallest = 2
  3-th smallest = 3
  4-th smallest = 4
  5-th smallest = 5
  6-th smallest = 5
  7-th smallest = 6
  8-th smallest = 7
  9-th smallest = 8
  10-th smallest = 9

K-th largest (1-indexed):
  1st largest = 9
  3rd largest = 7

Rank of (1-indexed):
  rank of 5 = 5
  rank of 1 = 1
  rank of 9 = 10
  rank of 6 = 7

Count in range:
  count < 5 = 4
  count in [3, 7] = 6
  count in [1, 10] = 10

Median (size=10):
  median (lower) = 5, (upper) = 5

Bedah Kode Baris-per-Baris #

typedef tree<pair<int, int>, null_type, less<pair<int, int>>, rb_tree_tag, tree_order_statistics_node_update> ost;: typedef untuk tree berbasis composite key. pair<int,int> di mana first = value, second = unique id untuk duplikat. Komparator lexicographic default.
tree.insert({val, counter_++}): setiap insert menambah pasangan (val, unique_id) dengan id monoton naik. Karena id unik, tidak ada konflik duplikat.
tree.lower_bound(make_pair(val, INT_MIN)) pada erase_one: cari elemen pertama dengan first >= val. Karena INT_MIN adalah second terkecil, ini menemukan elemen dengan first == val yang memiliki id terkecil (paling awal di-insert). Bila it->first == val, erase elemen ini. Untuk multiset, hanya satu kopi yang dihapus.
kth_smallest(k): find_by_order(k-1) memberi elemen ke-k dalam sorted order (0-indexed). Return it->first (value-nya saja).
kth_largest(k): indeks dari belakang = size() - k. find_by_order(size() - k) memberi elemen ke-k terbesar.
rank_of(val) = order_of_key({val, INT_MIN}) + 1: order_of_key menghitung elemen strictly less than (val, INT_MIN). Karena INT_MIN id terkecil, ini = jumlah elemen dengan value < val. Tambah 1 untuk rank 1-indexed. Bila val ada, rank = posisi pertama kemunculannya. Bila tidak ada, rank = posisi insert.
count_less_than(val) = order_of_key({val, INT_MIN}): jumlah elemen dengan value < val. Tanpa + 1.
count_in_range(lo, hi) = count_less_than(hi+1) - count_less_than(lo): inklusi lo dan hi. hi+1 sebagai batas exclusive.
Verifikasi:
- Input: {5,2,8,1,9,3,7,4,6,5} (10 elemen, 5 dua kali).
- Sorted: {1,2,3,4,5,5,6,7,8,9}. ✓
- kth_smallest(5) = 5, kth_smallest(6) = 5 (karena 5 ada dua kali). ✓
- 1st largest = 9, 3rd largest = 7. ✓ (9, 8, 7).
- rank_of(5) = 5 (empat elemen < 5: 1,2,3,4; rank pertama kemunculan 5 = 5). rank_of(1) = 1 (paling kecil). rank_of(9) = 10 (paling besar, muncul di posisi terakhir). rank_of(6) = 7 (enam elemen < 6: 1,2,3,4,5,5). ✓
- count < 5 = 4 (1,2,3,4). count [3,7] = 6 (3,4,5,5,6,7). count [1,10] = 10 (semua). ✓
- Median (size genap 10): elemen ke-5 dan ke-6 = 5, 5. Median = 5. ✓

Kompleksitas #

Operasi	Kompleksitas
insert	O(log n)
erase_one	O(log n)
kth_smallest / kth_largest	O(log n)
rank_of / count_less_than	O(log n)
count_in_range	O(log n) (dua order_of_key)
size	O(1)
Memori	O(n)

Aplikasi Lanjutan #

Sliding window dengan multiset: median stream data, k-th element dalam window geser.
Online rank leaderboard: real-time rank pemain dengan skor bisa sama.
Count inversions on stream: jumlah elemen lebih besar dari elemen saat ini sebelum insert.
Histogram dinamis: jumlah elemen di bucket range, update real-time.
Approximate quantile: p50, p90, p99 dengan kth_smallest pada size yang sesuai.

Ringkasan #

Order Statistics Tree = PBDS ordered set dengan dukungan multiset via composite key (value, unique_id).
API nyaman: insert, erase_one, kth_smallest, kth_largest, rank_of, count_less_than, count_in_range, median.
Kompleksitas O(log n) per operasi, memori O(n).
make_pair(val, INT_MIN) untuk query “kurang dari val” — eksplisit, bukan brace init.
Multiset support: unique_id monoton naik memastikan tidak ada konflik insert untuk elemen duplikat.
Aplikasi: leaderboard, sliding window median, online rank, dynamic histogram.