Ordered Set (Policy-Based Data Structures)
An indexed balanced tree for order statistics when std::set is not enough and a full custom BST is overkill.
Ordered Set (Policy-Based Data Structures)
The main note is rendered from the TeX source. Code lives in a separate C++ file so the write-up stays readable.
Overview
An ordered set gives me the normal balanced-BST operations plus order statistics: ``how many elements are smaller than \(x\)?'' and ``what is the \(k\)-th smallest element?'' In GNU C++, the practical contest version is usually PBDS (tree_order_statistics_node_update).
When to Use It
Use an ordered set when:
you need
insert,erase, and membership likestd::set,you also need
order_of_keyorfind_by_order,the constraints do not justify a custom treap or splay tree.
Typical uses are inversion-like online counts, median maintenance, k-th queries on a dynamic set, and duplicate-aware rank queries with the pair trick.
Core Idea
PBDS stores the set as a balanced tree augmented with subtree sizes. That subtree-size information is what powers:
order_of_key(x): number of elements strictly smaller than \(x\),find_by_order(k): iterator to the element with 0-indexed rank \(k\).
Key Insight
This note is really about picking the lightest tool that still matches the query pattern. If all I need is order statistics on one set, PBDS is usually the shortest correct answer. If I need split/merge, lazy tags, or custom aggregates, I should move to treap or splay instead.
Operations / Main Technique
insert and erase in \(O(\log n)\),
rank queries with
order_of_key,k-th queries with
find_by_order.
Duplicates.
The standard set version does not allow duplicates. The normal contest workaround is to store \(\texttt{pair<value, id>}\) so each insertion is unique while order is still controlled by the value first.
Correctness Intuition
The tree maintains sorted order exactly like std::set. The extra subtree-size metadata only summarizes how many keys lie below each node, which is exactly what rank and k-th queries need.
Complexity Analysis
insert / erase / find: \(O(\log n)\),
order_of_key: \(O(\log n)\),find_by_order: \(O(\log n)\).
Implementation
The code includes:
a plain ordered set alias,
a duplicate-friendly multiset wrapper based on \(\texttt{pair<value, id>}\).
This is GNU-specific, which is worth remembering before depending on it in a stricter environment.
Common Pitfalls
Forgetting that PBDS is not part of the C++ standard library.
Using
erase(value)in the duplicate case when the stored key is actually a pair.Treating
find_by_order(k)as 1-indexed when it is 0-indexed.Assuming the structure supports custom range aggregates the way a treap or segment tree would.
Variants / Extensions
Ordered map with the same policy update.
Treap or splay tree if split/merge or augmentation is needed.
Fenwick tree on compressed coordinates when the key universe is static enough.
Practice Problems
Maintain the median of a dynamic multiset.
Count how many previous values are smaller than the current one.
Answer k-th smallest queries under online insert and erase.
References
Code
Contest-ready reference implementation for the idea explained above.
using namespace __gnu_pbds;
template <class T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
struct OrderedMultiset {
ordered_set<pair<int, int>> os;
int next_id = 0;
void insert(int x) {
os.insert({x, next_id++});
}
bool erase_one(int x) {
auto it = os.lower_bound({x, -1});
if (it == os.end() || it->first != x) {
return false;
}
os.erase(it);
return true;
}
int order_of_key(int x) const {
return os.order_of_key({x, -1});
}
int kth(int k) const {
return os.find_by_order(k)->first;
}
int size() const {
return (int)os.size();
}
};
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.