Ordered Set

std::set STL mendukung insert, erase, find, dan lower_bound dalam O(log n), tetapi tidak bisa menjawab pertanyaan: “elemen ke-k terkecil berapa?” atau “berapa banyak elemen < x?”. Untuk persoalan itu, kita butuh ordered set — set terurut dengan dua operasi tambahan: find_by_order(k) (elemen ke-k, 0-indexed) dan order_of_key(x) (jumlah elemen < x). Keduanya O(log n). Library GNU PBDS (__gnu_pbds) menyediakan implementasi siap pakai berbasis Red-Black Tree augmented dengan size tracking. Pada Chapter ini kita pakai PBDS, membedah dua operasi utama, dan membahas trade-off versus struktur lain.

Aturan: Operasi yang Didukung #

Ordered set (__gnu_pbds::tree) mendukung seluruh operasi std::set ditambah:

• find_by_order(k): return iterator ke elemen ke-k (0-indexed). Bila k >= size(), return end().
• order_of_key(x): return jumlah elemen yang strictly less than x. Bila x ada di set, ini sama dengan index-nya.

Aplikasi langsung:

• Median: find_by_order(size() / 2).
• Rank elemen: order_of_key(x) + 1 (1-indexed rank).
• Count elemen < x: langsung order_of_key(x).
• Count elemen di range [l, r]: order_of_key(r+1) - order_of_key(l).

Mekanisme: Red-Black Tree Augmented #

PBDS tree memakai Red-Black Tree (default rb_tree_tag) atau Splay Tree (splay_tree_tag) sebagai backend. Setiap node menyimpan subtree size sebagai augmentasi. Saat insert/erase dan rotasi terjadi, ukuran subtree di-update naik ke root.

• find_by_order(k): berjalan dari root, di setiap node bandingkan k dengan size(left_subtree):
  • Bila k < size(left): rekursi ke kiri.
  • Bila k == size(left): node saat ini adalah jawabannya.
  • Bila k > size(left): k -= size(left) + 1, rekursi ke kanan.
• order_of_key(x): berjalan dari root, akumulasi size(left) saat belok ke kanan.

Keduanya O(log n) karena tinggi RB tree selalu O(log n).

Implementasi Ordered Set dengan PBDS #

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

using namespace std;
using namespace __gnu_pbds;

typedef tree<
    int,
    null_type,
    less<int>,
    rb_tree_tag,
    tree_order_statistics_node_update
> ordered_set;

int main() {
    ordered_set os;
    int vals[] = {5, 2, 8, 1, 9, 3, 7, 4, 6};
    for (int v : vals) os.insert(v);

    cout << "Ukuran: " << os.size() << '\n';
    cout << "Elemen sorted: ";
    for (int x : os) cout << x << ' ';
    cout << '\n';

    cout << "\nfind_by_order (k-th smallest, 0-indexed):\n";
    for (int k = 0; k < (int)os.size(); ++k) {
        cout << "  os[" << k << "] = " << *os.find_by_order(k) << '\n';
    }

    cout << "\norder_of_key (jumlah elemen < x):\n";
    cout << "  order_of_key(1) = " << os.order_of_key(1) << '\n';
    cout << "  order_of_key(5) = " << os.order_of_key(5) << '\n';
    cout << "  order_of_key(6) = " << os.order_of_key(6) << '\n';
    cout << "  order_of_key(10) = " << os.order_of_key(10) << '\n';

    cout << "\nSetelah erase(5):\n";
    os.erase(5);
    cout << "  size = " << os.size() << '\n';
    cout << "  os[4] = " << *os.find_by_order(4) << '\n';
    cout << "  order_of_key(6) = " << os.order_of_key(6) << '\n';
    return 0;
}

Output yang Dihasilkan:

Ukuran: 9
Elemen sorted: 1 2 3 4 5 6 7 8 9 

find_by_order (k-th smallest, 0-indexed):
  os[0] = 1
  os[1] = 2
  os[2] = 3
  os[3] = 4
  os[4] = 5
  os[5] = 6
  os[6] = 7
  os[7] = 8
  os[8] = 9

order_of_key (jumlah elemen < x):
  order_of_key(1) = 0
  order_of_key(5) = 4
  order_of_key(6) = 5
  order_of_key(10) = 9

Setelah erase(5):
  size = 8
  os[4] = 6
  order_of_key(6) = 4

Bedah Kode Baris-per-Baris #

1. #include <ext/pb_ds/assoc_container.hpp> dan tree_policy.hpp: header PBDS. Ini bagian dari GCC extension, bukan STL standar. Tersedia di g++ dan clang dengan libstdc++.
2. typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;: lima parameter template:
   • int: tipe key.
   • null_type: tipe mapped. null_type = set (key-only). Bila pakai int → map <int, int>.
   • less<int>: comparator. Default ascending. Untuk descending, ganti ke greater<int>.
   • rb_tree_tag: backend = Red-Black Tree. Alternatif: splay_tree_tag (amortized O(log n)).
   • tree_order_statistics_node_update: policy yang menambah augmentasi size subtree. Tanpa ini, find_by_order dan order_of_key tidak tersedia.
3. os.insert(v): insert elemen. O(log n).
4. for (int x : os): iterasi sorted. PBDS tree mendukung iterator bidirectional.
5. *os.find_by_order(k): return iterator ke elemen ke-k (0-indexed). Dereference untuk dapat value-nya. Bila k >= size(), return os.end().
6. os.order_of_key(x): jumlah elemen strictly less than x. Bila x ada di set, hasil = index x dalam sorted order. Bila x tidak ada, hasil = posisi insert jika x ditambahkan.
7. os.erase(5): hapus elemen dengan key 5. O(log n).
8. Verifikasi:
   • Awal os = {1,2,3,4,5,6,7,8,9}. os[4] = 5 (elemen ke-5 sorted).
   • order_of_key(1) = 0 (tidak ada elemen < 1). order_of_key(5) = 4 (empat elemen < 5: 1,2,3,4). order_of_key(6) = 5 (lima elemen < 6). order_of_key(10) = 9 (semua 9 elemen < 10). ✓
   • Setelah erase(5): os = {1,2,3,4,6,7,8,9} (8 elemen). os[4] = 6 (elemen ke-5 sekarang = 6 karena 5 dihapus). order_of_key(6) = 4 (empat elemen < 6: 1,2,3,4). ✓

Comparator Custom dan Multiset #

Untuk comparator custom:

// Multiset simulasi: pakai pair <key, unique_id>
typedef tree<
    pair<int, int>,
    null_type,
    less<pair<int, int>>,
    rb_tree_tag,
    tree_order_statistics_node_update
> ordered_multiset;

// Insert dengan unique id untuk mengizinkan duplikat
int id = 0;
ordered_multiset ms;
ms.insert({5, id++});
ms.insert({5, id++});
// order_of_key({5, INT_MIN}) = jumlah elemen < 5

PBDS tree tidak mendukung duplikat langsung. Trik: gunakan pair<key, unique_id> sebagai composite key dengan comparator lexicographic.

Kompleksitas dan Perbandingan #

Aplikasi #

1. Count inversion: untuk setiap elemen array, hitung order_of_key(x) sebelum insert. Total = jumlah inversi. O(n log n).
2. Sliding window median: ordered set menyimpan window. Median = find_by_order(size/2). Geser window: erase elemen keluar, insert elemen masuk.
3. K-th smallest in dynamic set: langsung find_by_order(k-1).
4. Range count: jumlah elemen dalam [l, r] = order_of_key(r+1) - order_of_key(l).
5. Online rank tracking: score board game — tambah skor, lihat rank pemain real-time.

Ringkasan #

• Ordered set (__gnu_pbds::tree) = std::set + find_by_order + order_of_key, semua O(log n).
• Backend Red-Black Tree dengan subtree-size augmentasi.
• find_by_order(k): elemen ke-k (0-indexed).
• order_of_key(x): jumlah elemen strictly less than x.
• Multiset simulasi: pakai pair<key, unique_id> dengan comparator lexicographic.
• Aplikasi: count inversion, sliding window median, k-th smallest, online rank.
• Untuk range value kecil, Fenwick lebih cepat. Untuk range besar dengan banyak update, ordered set natural.