Ordered Set / PBDS

std::set cannot answer “what is the $k$-th smallest?” or “how many elements are less than $x$?”. GNU C++ ships a policy-based data structure that can, in $O(\log n)$.

Setup

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
 
template<class T>
using ordered_set = tree<T, null_type, less<T>,
                         rb_tree_tag, tree_order_statistics_node_update>;

The two extra operations

ordered_set<int> s;
s.insert(5); s.insert(1); s.insert(9);
 
*s.find_by_order(0);        // 1  — the k-th smallest (0-indexed)
s.order_of_key(9);          // 2  — how many elements are strictly less than 9

Everything std::set offers still works: insert, erase, lower_bound, iteration.

Making a multiset

tree with less<T> rejects duplicates. Two workarounds:

1. Pair the value with a unique tiebreaker (recommended):

ordered_set<pair<int,int>> s;
int timer_ = 0;
s.insert({value, timer_++});
// count of elements < v:
s.order_of_key({v, -1});
// erase one occurrence:
s.erase(s.lower_bound({value, -1}));

2. Use less_equal<T> as the comparator. This allows duplicates but breaks find and erase(value) — they rely on a strict weak ordering. Only use it if you never need those, and prefer option 1.

Portability

GCC only

PBDS is a libstdc++ extension. It works on Codeforces, AtCoder and most judges, but not on MSVC or libc++ (Clang on macOS). If portability matters, use one of the alternatives below.

The alternatives

Approach	Preprocessing	Query	Notes
PBDS tree	—	$O(\log n)$	shortest code
BIT over compressed values	$O(n\log n)$	$O(\log n)$	faster, portable; needs values known in advance
BIT with binary lifting descent	—	$O(\log n)$	$k$-th smallest in one descent, no extra log
Segment tree over values	—	$O(\log n)$	supports more aggregates
Treap with subtree sizes	—	$O(\log n)$	fully customisable
Sqrt decomposition over values	—	$O(\sqrt{n})$	simplest to reason about

BIT with $k$-th smallest descent

When the value range is known, this is the fastest option — one $O(\log n)$ descent, no binary search on top:

int kth(int k) {                     // k-th smallest, 1-indexed
    int pos = 0;
    for (int pw = 1 << LOG; pw; pw >>= 1)
        if (pos + pw <= n && bit[pos + pw] < k) { pos += pw; k -= bit[pos]; }
    return pos + 1;
}

What ordered sets solve

Problem	Method
Count inversions	insert right to left, order_of_key
$k$-th smallest in a growing set	find_by_order
Rank of an element	order_of_key
Count elements in $[l,r]$	order_of_key(r+1) - order_of_key(l)
Running median	find_by_order(size()/2)
Count pairs $(i,j)$ with $i<j$ and $a_i>a_j$	inversions
Sliding window $k$-th smallest	insert and erase as the window moves

Other PBDS containers

gp_hash_table is a fast open-addressing hash map — typically 3-5× faster than unordered_map and, with a custom hash, resistant to anti-hash tests:

#include <ext/pb_ds/assoc_container.hpp>
gp_hash_table<long long, int> h;

Add a randomised hash (splitmix64 with a time-based seed) if the keys are adversarial; the default hash for integers is the identity, which is trivially hackable.

See also: Fenwick Tree · Balanced BSTs · STL Containers