C++ Module 19 – C++ for DSA and competitive programming

Order-statistics trees with __gnu_pbds (GCC only)

k-th element and rank queries in O(log n) with __gnu_pbds::tree, duplicates without the less_equal trap, and a portable Fenwick tree for other compilers.

Advanced
20 minutes
Examples run with Clang 21.0.0, GCC 16.2.0 and Python 3.14.8
By MySmartCoPilot

Free: Five template arguments declare an order-statistics tree · Subtree sizes answer both queries in one walk · Duplicates, inversions and other compilers decide the design · Practise. With a pass: 2 in-depth parts and 3 interview answers, about 12 minutes.

What you will learn

Use tree with tree_order_statistics_node_update as an ordered set
Answer k-th element and rank queries with find_by_order and order_of_key
Store duplicates safely and count inversions
Use a portable Fenwick-tree alternative on any compiler

Before you start

What you’ll learn · Before you start

What you will learn

Use tree with tree_order_statistics_node_update as an ordered set
Answer k-th element and rank queries with find_by_order and order_of_key
Store duplicates safely and count inversions
Use a portable Fenwick-tree alternative on any compiler

Before you start

On this page

An A balanced search tree whose nodes also store the size of their subtree, so that it can return the k-th smallest element and count the elements below a value, both in O(log n). is a sorted set that can also say which element is k-th in order and how many elements are smaller than a value, both in O(log n). std::set cannot: it keeps its elements sorted, but reaching the k-th one takes k steps with std::next, and counting the elements below a value takes std::distance, again linear. GCC’s standard library, libstdc++, ships an extension that can. Its An extension of libstdc++, GCC's standard library, in the namespace __gnu_pbds: trees, hash tables and other containers whose behaviour is chosen by template arguments called policies. include __gnu_pbds::tree, and with the node-update policy tree_order_statistics_node_update every node also stores the size of its subtree, which gives two new member functions: find_by_order(k) returns the element at position k, counting from 0, and order_of_key(x) returns how many elements are smaller than x. It works with GCC, and with Clang only when Clang uses libstdc++; Apple clang’s libc++ and Microsoft’s library do not have it. For those, a An array in which cell i holds the total of a range of positions that ends at i, so that the total of any prefix, and an update of one position, take O(log n) steps. Also called a binary indexed tree. over the sorted values answers the same queries portably.

Five template arguments declare an order-statistics tree

ordered_set.cpp C++ · ordered_set.cpp

// An order-statistics tree from libstdc++'s policy-based data structures: a set that also answers "which element
// is k-th?" and "how many elements are smaller than x?" in O(log n).
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <functional>
#include <print>

template <class T>
using ordered_set = __gnu_pbds::tree<T, __gnu_pbds::null_type, std::less<T>, __gnu_pbds::rb_tree_tag,
                                     __gnu_pbds::tree_order_statistics_node_update>;

int main() {
  ordered_set<int> s;
  for (int x : {40, 12, 31, 5, 23, 19}) s.insert(x);

  std::print("in order:");
  for (int x : s) std::print(" {}", x);
  std::println("");
  std::println("find_by_order(0) = {}, find_by_order(3) = {}", *s.find_by_order(0), *s.find_by_order(3));
  std::println("order_of_key(20) = {}, order_of_key(5) = {}, order_of_key(100) = {}",
               s.order_of_key(20), s.order_of_key(5), s.order_of_key(100));
  std::println("find_by_order(6) is end(): {}", s.find_by_order(6) == s.end());

  // The median of the six values: the elements at positions 2 and 3.
  std::println("median: ({} + {}) / 2", *s.find_by_order(2), *s.find_by_order(3));

  s.erase(12);
  std::println("after erase(12): order_of_key(20) = {}, find_by_order(1) = {}", s.order_of_key(20), *s.find_by_order(1));
}

Rank and k-th queries with GCC, and what Apple clang says Python · ordered_set_session.py

from session import run

# GCC with libstdc++; then Apple clang, whose libc++ has no policy-based data structures.
run("""
g++-16 -std=c++23 -Wall -Wextra ordered_set.cpp -o ordered_set && ./ordered_set
clang++ -std=c++23 ordered_set.cpp -o ordered_set-clang 2>&1 | grep -m1 error
""")

Output

$ g++-16 -std=c++23 -Wall -Wextra ordered_set.cpp -o ordered_set && ./ordered_set
in order: 5 12 19 23 31 40
find_by_order(0) = 5, find_by_order(3) = 23
order_of_key(20) = 3, order_of_key(5) = 0, order_of_key(100) = 6
find_by_order(6) is end(): true
median: (19 + 23) / 2
after erase(12): order_of_key(20) = 2, find_by_order(1) = 19
$ clang++ -std=c++23 ordered_set.cpp -o ordered_set-clang 2>&1 | grep -m1 error
ordered_set.cpp:3:10: fatal error: 'ext/pb_ds/assoc_container.hpp' file not found

Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 ordered_set_session.py

The declaration passes five template arguments: the key, the mapped type, here null_type because this is a set and not a map, the comparator: A function that takes two elements and returns true when the first must come before the second, such as [](int a, int b) { return a > b; } for the highest first. Sorting algorithms and ordered containers call it for every comparison they make. More in “Essential C++ algorithms: find, sort, partition”, the tree’s balancing scheme, rb_tree_tag for a red-black tree: A binary search tree that marks each node red or black and recolours and rotates nodes on every insertion and erasure to stay balanced, so that a lookup visits O(log n) nodes. libc++ and libstdc++ build std::map and std::set as red-black trees. More in “Choosing a C++ container: complexity and speed”, and the node-update policy that adds the two queries. An alias such as ordered_set keeps the declaration readable. Iterating gives the values in order, like a std::set. find_by_order(3) returned 23, the fourth smallest, and order_of_key(20) returned 3, because 5, 12 and 19 are smaller; asking for position 6 of a six-element set returned end(). find_by_order also gives a median in O(log n) at any moment, here 19 and 23, the elements at positions 2 and 3. After erasing 12 both answers moved, and they stay correct after every insertion and erasure. The last command shows the portability limit: Apple clang stops at the first line with “‘ext/pb_ds/assoc_container.hpp’ file not found”.

Checkpoint

Check: Declaring the tree and its two queries

Question 1 of 2 In the ordered_set alias, what does __gnu_pbds::null_type as the second template argument make the tree?
Choose one answer.

A map whose values all start as zero A tree without the order-statistics queries A set, with no value mapped to each key A tree that accepts null pointers as keys

Show the answer: Question 1 of 2

Answer: A set, with no value mapped to each key

The five arguments are the key, the mapped type (null_type for a set), the comparator, the balancing scheme (rb_tree_tag) and the node-update policy that adds find_by_order and order_of_key.
Question 2 of 2 The tree holds 5, 12, 19, 23, 31 and 40. What does order_of_key(31) return?
Type a number.
Your answer elements

Show the answer: Question 2 of 2

Answer: 4 elements

order_of_key(x) counts the elements smaller than x: 5, 12, 19 and 23 are smaller than 31, so it returns 4, which is also the position of 31 counted from 0.

Subtree sizes answer both queries in one walk

Subtree sizes, the extra field that answers rank and k-th queries

Text description of the diagram

A binary search tree with six nodes. Each node shows its value and the size of its subtree, the node itself included.

The root is 23, with size 6: the whole tree.
Its left child is 12, with size 3; the children of 12 are 5 on the left and 19 on the right, each with size 1.
Its right child is 31, with size 2; the only child of 31 is 40, on the right, with size 1.

find_by_order(3) starts at the root: the left subtree of 23 holds 3 elements, positions 0 to 2, so 23 itself is at position 3. order_of_key(20) walks down too: 20 is smaller than 23, so it goes left to 12; 20 is larger than 12, so it counts the left subtree of 12 and 12 itself, 1 + 1, and goes right to 19; 20 is larger than 19, so it counts 0 + 1 more; the walk ends, and 3 elements are smaller than 20.

Every node knows how many nodes lie in its subtree, itself included, and the tree updates these sizes along the path of every insertion, erasure and rebalancing rotation, which costs O(log n) as the rest of the operation does. With sizes, each query walks down from the root once and never climbs back. find_by_order(k) compares k with the size of the left subtree: if k is smaller, the answer is on the left; if it is equal, the current node is the answer; otherwise it subtracts the left size and one more for the node, and goes right. order_of_key(x) goes down as a search for x does, and whenever it goes right it adds the size of the left subtree plus one, the elements it has just passed; if it meets x itself, it adds that node’s left size and stops. On the tree in the diagram, find_by_order(3) stops at the root, whose left subtree holds 3 elements, and order_of_key(20) passes three nodes. Each answer therefore costs at most one step per level of a balanced tree: about log₂ n steps, 20 for a million elements.

Step through the search for 20 in the same six values, inserted root first so that the tree is the one in the diagram; libstdc++’s own tree may be shaped differently, and its sizes give the same answers. order_of_key(20) walks this path and adds, at each turn to the right, the left subtree’s size plus one: 1 + 1 at 12 and 0 + 1 at 19, so 3 elements are smaller than 20.

Interactive · step through it The path of order_of_key(20) through the six values Each comparison picks one subtree and rules out the other.

being compared or looked at
visited or ruled out

Pseudo-code

curr ← root
while curr ≠ null:
if x = curr.key: return curr
if x < curr.key: curr ← curr.left
else: curr ← curr.right
return "not found"

Search the tree for 20. Each comparison sends the search into one subtree and rules the other out.

When it finishes: 20 not found.

Comparisons 0

Text Sorter Sort a list of numbers to check a k-th element or a rank by hand: the value at line k + 1 is find_by_order(k).

Three ways to answer rank and k-th queries
Criterion	__gnu_pbds::tree	std::set	Fenwick tree
k-th element	O(log n)	O(k) with std::next	O(log n)
Elements below x	O(log n)	O(n) with std::distance	O(log n)
Insert and erase	O(log n)	O(log n)	O(log n)
Values unknown in advance	Yes	Yes	Only if they are small integers
Compilers	GCC, or Clang with libstdc++	All	All
When to choose	A GCC judge and values that arrive one by one	Sorted iteration without rank queries	Any compiler, values known before the queries

Key idea

Store the size of every subtree in its root, and both queries become one walk down the tree: find_by_order subtracts the left sizes it passes, and order_of_key adds them.

Checkpoint

Check: How subtree sizes answer both queries

Question 1 of 2 find_by_order(k) stands at a node whose left subtree holds 3 elements. Where does it go when k is 1?
Choose one answer.

Into the right subtree, looking for position 1 - 3 - 1 Into the left subtree, still looking for position 1 Back up to the parent It stops; this node is the answer

Show the answer: Question 1 of 2

Answer: Into the left subtree, still looking for position 1

At each node find_by_order compares k with the size of the left subtree: smaller goes left, equal stops at the node, larger subtracts the left size and one for the node and goes right.
Question 2 of 2 On the diagram's tree (root 23 with a left subtree of 3, right child 31 with only a right child, 40), what value does find_by_order(4) return?
Type a number.
Your answer

A hint

At 23, compare 4 with the left size, 3.

Show the answer: Question 2 of 2

Answer: 31

At 23, 4 is larger than the left size 3, so the walk subtracts 3 and one for 23, leaving 0, and goes right to 31. The left subtree of 31 is empty, size 0, which equals k, so 31 is the element at position 4.

Duplicates, inversions and other compilers decide the design

Four things decide whether a solution built on this tree is right and will compile:

Choice	What it does
less_equal as the comparator	Lets duplicates in but breaks find, erase and the two bounds.
Pairs of a value and a unique id	Make every element distinct, which is the safe way to keep duplicates.
Counting A pair of positions, one before the other, whose values are out of order, the earlier value being the larger. A sorted array has none, and an array in decreasing order has the most, n(n − 1) / 2.	Takes one order_of_key query per element, O(n log n) in all.
A Fenwick tree	Built over the sorted distinct values, it counts the copies of each value and answers both queries on any compiler.

The first two decide whether duplicates are counted right; the last two are what the tree is used for and what replaces it where libstdc++ is missing.

Checkpoint

Check: Duplicates, inversions and other compilers

Question 1 of 2 Which way keeps duplicate values in the order-statistics tree safely?
Choose one answer.

Store pairs of the value and a unique id Nothing is needed; the tree keeps duplicates Keep a second tree for the copies Use std::less_equal as the comparator

Show the answer: Question 1 of 2

Answer: Store pairs of the value and a unique id

The tree keeps one element per key, so duplicates need distinct keys: (value, id) pairs with an id that is never reused.
Question 2 of 2 A judge builds with Microsoft's compiler, and all the values are given before the queries. What answers rank and k-th queries in O(log n)?
Choose one answer.

std::set with std::distance A Fenwick tree over the sorted distinct values std::set with std::next __gnu_pbds::tree

Show the answer: Question 2 of 2

Answer: A Fenwick tree over the sorted distinct values

The comparison table's last column fits: any compiler, with the values known before the queries. The policy-based tree exists only where libstdc++ does.

Practise

Begin anywhere: the questions adapt to your answers and explain every choice.

Duplicates and inversions with pb_ds, reproduced and measured Pro: opens with a Pro, Premium or Ultimate pass

Most wrong answers with this tree come from duplicates, and one of its classic uses is counting inversions. This part reproduces what less_equal breaks, builds a multiset that works, and measures inversion counting against merge sort and a brute force.

In this part:

A comparator that is not strict, reproduced
A multiset done right: value and id pairs
Counting inversions with rank queries, measured

6 runnable examples (C++, Python) · about 6 minutes

Opening this part with your pass…

This part opens with any MySmartCoPilot pass.

Pro pass · 1 week₹79$2.99
30 days₹179$5.99
1 year₹1,699$45

One payment; a pass never renews. The price shown is the total you pay: no fees or charges are added at checkout.

Choose a pass I have a licence key

It also opens every other in-depth part in Learn and every Pro tool. Sales are final, except where the law gives you a right to withdraw, for example in the EU and the UK (refund policy).

A portable Fenwick tree for rank and k-th queries, stress-tested Pro: opens with a Pro, Premium or Ultimate pass

On Apple clang, Microsoft’s compiler or a judge without libstdc++ the same queries need a different structure. This part builds one from a Fenwick tree, proves it against a reference and the pb_ds tree, measures it, and ends with an exercise that uses both.

In this part:

Prefix counts and a k-th search by binary lifting
Stress-tested against a reference and the GCC tree
Measured: Fenwick against the GCC tree on half a million values
Your turn: a stream of insertions, erasures, ranks and k-th queries

1 diagram · 9 runnable examples (C header, C++, Python) · about 9 minutes

Opening this part with your pass…Pro part. It opens with the same pass as the part above.

Interview questions

Fresher to mid · Warm-up

In a __gnu_pbds order-statistics tree, what do find_by_order and order_of_key return, and how fast are they?

find_by_order(k) returns an iterator to the element at position k in sorted order, counting from 0, or end() when k is not smaller than the size. order_of_key(x) returns how many elements are smaller than x, which is also the position x would take if it were inserted. Both take O(log n), because the policy tree_order_statistics_node_update makes every node store the size of its subtree, so each query walks from the root to a leaf once, deciding at each node by the size of the left subtree. A std::set keeps the same order but has no sizes, so the same questions take linear time with std::next or std::distance.
Fresher to mid

A solution keeps a multiset in a __gnu_pbds tree ordered by std::less_equal<int>, so that duplicates are allowed. It passes the samples, but on hidden tests values that should have been removed are still counted. Explain the bug and fix the data structure without losing O(log n) operations.

Model answer, Pro. Model answers open with any pass; prices are in the notice on this page. First step and follow-ups
Mid

Your solution answers k-th smallest and rank queries with a __gnu_pbds tree, and now the same code must build with Apple clang and with Microsoft's compiler. Design a portable replacement, state what it needs to know in advance, and say how you would show that it gives the same answers.

Model answer, Pro. First step and follow-ups
Mid to senior

Up to 10^6 numbers arrive one at a time, and after each one the program must print the median of all numbers so far. Some numbers are later withdrawn again. Compare two heaps, an order-statistics tree and a Fenwick tree for this, and choose one for a GCC judge and one for any compiler.

Model answer, Pro. First step and follow-ups

Key takeaways

__gnu_pbds::tree with tree_order_statistics_node_update adds find_by_order(k) and order_of_key(x), both O(log n).
It is part of libstdc++: GCC builds it, Apple clang and Microsoft’s compiler do not.
Keep duplicates as (value, id) pairs, never with less_equal.
A Fenwick tree over sorted values answers the same queries on any compiler when the values are known first.

References

The GNU C++ Library Manual: Policy-Based Data Structures (GNU Project)
The GNU C++ Library Manual: Policy-Based Data Structures, design (GNU Project)
AtCoder language and library list (AtCoder)
Working Draft, Programming Languages: C++ (N4950), associative containers and iterator operations (ISO/IEC JTC1/SC22/WG21)
A New Data Structure for Cumulative Frequency Tables (Peter M. Fenwick) (Software: Practice and Experience (Wiley))

Report a problem with this lesson

In this module: C++ for DSA and competitive programming

Online judge C++ compilers, flags and limits Free lesson, Pro answers: 20 minutes
A clean C++ contest template, and habits to avoid Free core, Pro depth: 8 of 20 minutes free
Fast C++ input and output for online judges Free core, Pro depth: 8 of 20 minutes free
The STL toolkit for DSA in C++ Free core, Pro depth: 8 of 20 minutes free
Custom comparators and strict weak ordering Free core, Pro depth: 8 of 20 minutes free
C++ binary search: lower_bound and partition_point Free core, Pro depth: 7 of 20 minutes free
Overflow, __int128 and modular arithmetic Free core, Pro depth: 7 of 20 minutes free
C++ unordered_map: custom hashes and anti-hash tests Free core, Pro depth: 8 of 20 minutes free
Order-statistics trees with __gnu_pbds (GCC only) Free core, Pro depth: 8 of 20 minutes free
Deep recursion, stack limits and iterative DFS Free core, Pro depth: 7 of 20 minutes free
Stress testing contest solutions in C++ Free core, Pro depth: 11 of 30 minutes free

Your country

Order-statistics trees with __gnu_pbds (GCC only)

What you will learn

Before you start

What you will learn

Before you start

Five template arguments declare an order-statistics tree

Subtree sizes answer both queries in one walk

Duplicates, inversions and other compilers decide the design

Practise

Duplicates and inversions with pb_ds, reproduced and measured Pro: opens with a Pro, Premium or Ultimate pass

A portable Fenwick tree for rank and k-th queries, stress-tested Pro: opens with a Pro, Premium or Ultimate pass

Interview questions

In a __gnu_pbds order-statistics tree, what do find_by_order and order_of_key return, and how fast are they?

A solution keeps a multiset in a __gnu_pbds tree ordered by std::less_equal<int>, so that duplicates are allowed. It passes the samples, but on hidden tests values that should have been removed are still counted. Explain the bug and fix the data structure without losing O(log n) operations.

Your solution answers k-th smallest and rank queries with a __gnu_pbds tree, and now the same code must build with Apple clang and with Microsoft's compiler. Design a portable replacement, state what it needs to know in advance, and say how you would show that it gives the same answers.

Up to 10^6 numbers arrive one at a time, and after each one the program must print the median of all numbers so far. Some numbers are later withdrawn again. Compare two heaps, an order-statistics tree and a Fenwick tree for this, and choose one for a GCC judge and one for any compiler.

Key takeaways

References

Related tools