← all categories

Pbds Order Statistics Tree 92dca843

Order-statistics tree via GCC's built-in policy-based tree. find_by_order(k) gives the kth smallest element (0-indexed, as an iterator); order_of_key(x) gives the count of elements strictly less than x. Fastest option when it fits, but no split/merge and no direct erase-by-value (erase by iterator); for those, or for duplicate keys, use treap-ordered.h or splay-ordered-set.h instead.

Time: O(\log n) per operation. tested

content/data-structures/pbds-order-statistics-tree.h

#undef int  // pb_ds headers use 'int' internally; #define int long long corrupts them
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define int long long
using namespace __gnu_pbds;

template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

// usage:
//   ordered_set<int> s;
//   s.insert(5);
//   *s.find_by_order(0);   // smallest element
//   s.order_of_key(5);     // # elements < 5
//   s.erase(s.find_by_order(0));