The treap Data Structure

Usage: #include "bst.h"

The library's binary search trees, sorted dictionaries and sorted sets are all treaps: binary search trees in which every key also has a priority, and no key has a higher priority than the key above it. Five types are built on the treap:

• par::treap<K, V>, a binary search tree with keys of type K and values of type V;
• par::aug_treap<K, V, Combine, Identity>, an augmented tree;
• par::treap_dict<K, V>, a sorted dictionary;
• par::aug_treap_dict<K, V, Combine, Identity>, an augmented sorted dictionary;
• par::treap_set<K>, a sorted set.

They satisfy the concepts described on the tree, dictionary and set concepts page.

Persistence. Like everything in the library, they are persistent: no operation changes its arguments, and an update returns a new tree, dictionary or set that shares most of its nodes with the old one. Copying one takes constant time, because the copy shares all of its nodes.

Type requirements. Keys must be totally ordered, comparable with ==, !=, <, <=, > and >=, and keys and values must be copyable. A key's priority is a hash of the key when the key type has a std::hash, as numbers and strings do, and pairs and tuples of them. Otherwise the priority is random, and code that rebuilds a tree from its own pieces with join_mid still produces a correct treap, but can do more work, since every rebuilt node draws a new priority.

Cost bounds. In the costs below, $n$ is the size of the tree, dictionary or set, and comparing keys, hashing them and combining values are assumed to take constant time. A bound marked * holds with high probability, and one marked † holds in expectation. Unmarked bounds are deterministic. Hovering over a marked bound also says which.

Trees

par::treap<K, V> is a binary search tree: it satisfies par::bst, so it has the four operations from lecture, empty, size, expose and join_mid. The library also provides split and join for every tree, and the concepts page shows how to write others. In the signatures below, Tree is the tree's type. A tree is built up from empty with join_mid:

using tree = par::treap<int, std::string>;

auto leaf = [](int k, std::string v) { return join_mid(tree::empty(), k, v, tree::empty()); };
tree t = join_mid(leaf(1, "a"), 2, "b", leaf(3, "c"));

static auto empty() -> Tree

Returns the empty tree. Declaring a tree with no initializer, as in tree t;, gives the empty tree too.

auto size() const -> std::size_t

Returns the number of keys in the tree. For the tree t above, t.size() is 3.

auto expose(const Tree& t) -> std::optional<par::node_view<Tree>>

template<typename Tree>
struct node_view {
  const Tree& left;
  const K& key;
  const V& value;
  const Tree& right;
};

Returns nothing for the empty tree, and otherwise a view of the root: its left subtree, its key and value, and its right subtree. The view refers into t rather than copying from it, so it is only valid while t is. Copy out anything you want to keep; copying a subtree takes constant time. Exposing a temporary tree does not compile, since the view would refer into a tree that is about to be destroyed.

if (auto e = expose(t)) {
  auto [left, key, value, right] = e.value();
  // key == 2 and value == "b", and left and right are the subtrees
}

auto join_mid(Tree L, const K& k, const V& v, Tree R) -> Tree

Returns a tree holding every pair of L, the pair (k, v), and every pair of R. Requires every key of L to be less than k, and k to be less than every key of R. This is where the treap balances, so the result need not have k at its root.

auto split(
  const Tree& t,
  const K& k
) -> std::tuple<Tree, std::optional<V>, Tree>

Returns (L, v, R), where L holds the pairs of t with keys strictly less than k, R the pairs with keys strictly greater than k, and v the value at k, or nothing if k is not in t.

auto [L, v, R] = split(t, 2);    // L holds key 1, v holds "b", and R holds key 3

auto join(const Tree& L, const Tree& R) -> Tree

Returns a tree holding every pair of L and R. Requires every key of L to be less than every key of R.

tree without2 = join(L, R);    // the tree of keys 1 and 3

Creating Dictionaries

par::treap_dict<K, V> is a sorted dictionary: it satisfies par::sorted_dict. An operation on one dictionary is a member function, as in d.find(k); an operation on two dictionaries is a free function, as in set_union(a, b); and the operations that make a dictionary from scratch are static, as in dict::from_sequence(pairs). In the signatures below, Dict is the dictionary's type, and the examples use this dictionary:

using dict = par::treap_dict<int, std::string>;

par::array_sequence<std::pair<int, std::string>> pairs{{3, "c"}, {1, "a"}, {5, "e"}};

// Creates the dictionary {1 -> a, 3 -> c, 5 -> e}
auto d = dict::from_sequence(pairs);

static auto empty() -> Dict
static auto singleton(K k, V v) -> Dict

empty returns the empty dictionary, and singleton the dictionary holding just k mapped to v. Declaring a dictionary with no initializer gives the empty dictionary too.

auto one = dict::singleton(2, "b");    // {2 -> b}

static auto from_sequence(const sequence auto& pairs) -> Dict

Returns the dictionary of a sequence of key-value pairs, which may be in any order. If a key appears more than once, the value of its first occurrence is kept. The elements may be std::pairs or any other type with two parts, such as a two-element std::tuple. Here $n$ is the length of the sequence.

par::array_sequence<std::pair<int, std::string>> repeats{{2, "b"}, {1, "a"}, {2, "z"}};

// Creates the dictionary {1 -> a, 2 -> b}: the first value of 2 is kept
auto r = dict::from_sequence(repeats);

Converting and Printing

auto to_sequence() const -> par::array_sequence<std::pair<K, V>>

Returns the key-value pairs of the dictionary in increasing order of key.

auto s = d.to_sequence();    // the pairs (1, a), (3, c) and (5, e), in that order

auto operator<<(std::ostream& out, const Dict& d) -> std::ostream&

Prints the dictionary, with its pairs in increasing order of key. The key and value types must be printable with << themselves.

std::cout << d;    // prints {1 -> a, 3 -> c, 5 -> e}

Basic Operations

auto size() const -> std::size_t

Returns the number of keys in the dictionary. d.size() is 3.

auto find(const K& k) const -> std::optional<V>

Returns a copy of the value at k, or nothing if k is not in the dictionary.

auto c = d.find(3);    // an optional holding "c"
auto x = d.find(4);    // std::nullopt

auto insert(K k, V v) const -> Dict

Returns the dictionary with k mapped to v. If k is already present, its value is replaced. Like every update, insert leaves d unchanged and returns a new dictionary, so be sure to use the result.

auto d2 = d.insert(4, "d");    // {1 -> a, 3 -> c, 4 -> d, 5 -> e}
auto d3 = d.insert(3, "C");    // {1 -> a, 3 -> C, 5 -> e}

auto remove(const K& k) const -> Dict

Returns the dictionary without the key k. If k is not present, the result holds the same pairs as d.

auto d4 = d.remove(3);    // {1 -> a, 5 -> e}

auto filter(auto&& p) const -> Dict

Returns the pairs (k, v) for which p(k, v) is true. The predicate takes both the key and the value.

auto big = d.filter([](int k, const std::string&) { return k >= 3; });    // {3 -> c, 5 -> e}

Extremes and Neighbors

first, last, prev and next return a pair of references into the dictionary's nodes rather than copies, as select does. They stay valid as long as d, or another dictionary that shares those nodes, is alive. Copy out what you want to keep.

auto first() const -> std::optional<std::pair<const K&, const V&>>
auto last() const -> std::optional<std::pair<const K&, const V&>>

Return the pair with the smallest key, or the largest, or nothing if the dictionary is empty.

auto [k, v] = *d.first();    // k == 1 and v == "a"

auto prev(
  const K& k
) const -> std::optional<std::pair<const K&, const V&>>

auto next(
  const K& k
) const -> std::optional<std::pair<const K&, const V&>>

prev returns the pair with the largest key strictly less than k, and next the pair with the smallest key strictly greater than k, or nothing if there is no such key. k need not be in the dictionary.

auto p = d.prev(4);    // the pair (3, c)
auto q = d.next(5);    // std::nullopt

Order Statistics

auto rank(const K& k) const -> std::size_t

Returns the number of keys strictly less than k, which need not be in the dictionary.

auto below = d.rank(4);    // 2

auto select(
  std::size_t i
) const -> std::optional<std::pair<const K&, const V&>>

Returns the pair whose key has rank i, or nothing if i is at least the size of the dictionary. Ranks start at zero, so select(0) is the pair with the smallest key. Like first, it returns references into the dictionary's nodes.

auto second = d.select(1);    // the pair (3, c)

Splitting and Joining

auto split(
  const K& k
) const -> std::tuple<Dict, std::optional<V>, Dict>

Returns (L, v, R), where L holds the pairs with keys strictly less than k, R the pairs with keys strictly greater than k, and v the value at k, or nothing if k is not present.

auto [L, v, R] = d.split(3);    // L is {1 -> a}, v holds "c", and R is {5 -> e}

auto get_range(const K& k1, const K& k2) const -> Dict

Returns the pairs whose keys k satisfy k1 <= k < k2. The range includes k1 but not k2.

auto low = d.get_range(1, 5);    // {1 -> a, 3 -> c}

auto join(const Dict& a, const Dict& b) -> Dict

Returns every pair of a and b. Requires every key of a to be less than every key of b.

auto [L, v, R] = d.split(3);
auto without3 = join(L, R);    // {1 -> a, 5 -> e}

Set-Theoretic Operations

In the costs below, $n$ and $m$ are the sizes of the two dictionaries, with $m \leq n$. The examples use d and this second dictionary:

par::array_sequence<std::pair<int, std::string>> others{{3, "C"}, {4, "D"}};

// Creates the dictionary {3 -> C, 4 -> D}
auto o = dict::from_sequence(others);

auto set_union(const Dict& a, const Dict& b) -> Dict

Returns the pairs whose keys are in a or b. A key in both keeps its value from a. The name is set_union because union is a C++ keyword.

auto u = set_union(d, o);    // {1 -> a, 3 -> c, 4 -> D, 5 -> e}

auto set_intersection(const Dict& a, const Dict& b) -> Dict

Returns the pairs of a whose keys are also in b.

auto i = set_intersection(d, o);    // {3 -> c}

auto set_difference(const Dict& a, const Dict& b) -> Dict

Returns the pairs of a whose keys are not in b.

auto diff = set_difference(d, o);    // {1 -> a, 5 -> e}

Sets

par::treap_set<K> is a sorted set: it satisfies par::sorted_set. A set is a dictionary without values, and each operation means what the dictionary's does on keys alone, with the same cost. The operations below differ by more than dropping the value, and in their signatures Set is the set's type. Besides these, first, last, prev, next and select return a copy of the key, std::optional<K>, rather than references.

using int_set = par::treap_set<int>;

par::array_sequence<int> keys{5, 1, 3, 1};

// Creates the set {1, 3, 5}
auto s = int_set::from_sequence(keys);

static auto from_sequence(const sequence<K> auto& keys) -> Set

Returns the set of the keys in a sequence, which may be in any order and contain duplicates. Here $n$ is its length.

auto contains(const K& k) const -> bool

Returns whether k is in the set. It is the set's version of find.

bool three = s.contains(3);    // true

auto filter(auto&& p) const -> Set

Returns the keys k for which p(k) is true.

auto big = s.filter([](int k) { return k >= 3; });    // {3, 5}

auto split(const K& k) const -> std::tuple<Set, bool, Set>

Returns (L, found, R), where L holds the keys strictly less than k, R the keys strictly greater, and found whether k is present.

auto [lo, found, hi] = s.split(3);    // lo is {1}, found is true, and hi is {5}

Augmentation

par::aug_treap and par::aug_treap_dict are augmented: besides their pairs, each keeps all of its values combined into one, which reduced_val returns in constant time. Two template parameters say how values combine:

• Combine, an associative function that combines two values;
• Identity, the identity of Combine: combining it with any value x, on either side, gives back x.

The combined values have a type the dictionary calls augmented_value_type, which is usually the value type itself. It is the widest of the types of the values, Identity and Combine's results, so an identity of 0 sums long values as longs.

The two parameters are values, not types: write std::plus<>{} for addition, or give a lambda with no captures by its name. Identity must be a structural type, one that can be a template argument: numbers, std::pairs, and structs whose members are all public and structural. std::string and std::optional are not, but std::nullopt is, and it serves as the identity when the combined values are optionals.

auto reduced_val() const -> augmented_value_type

Returns the values combined with Combine in increasing order of their keys, or Identity if the tree or dictionary is empty.

Together with get_range, which takes logarithmic time, reduced_val gives the combined value of any range of keys in logarithmic time, without visiting the values in the range.

Example: Shop Profits

The examples below ask different questions of one week of a shop's daily profit, keyed by day. The shop lost money on days 3 and 5:

// (day, profit) pairs for one week
par::array_sequence<std::pair<int, int>> week{{1, 10}, {2, 30}, {3, -25}, {4, 30}, {5, -15}};

Total profit. Addition is a monoid on integers: Combine is std::plus<>{}, and its identity is 0, since adding 0 changes nothing. With these, reduced_val of a range is the total profit over those days:

using totals_dict = par::aug_treap_dict<int, int, std::plus<>{}, 0>;

auto totals = totals_dict::from_sequence(week);
int midweek = totals.get_range(2, 5).reduced_val();    // 30 - 25 + 30 = 35

get_range(2, 5) includes 2 but not 5, so it holds days 2, 3 and 4.

The best day. Now suppose we want the most profitable day in a range. That takes two changes.

First, the answer is a day, but reduced_val only combines values; it never sees the keys. So each value has to carry its own day along with its profit, and Combine keeps whichever of its two arguments has the larger profit.

Second, Combine needs an identity: a value that it always discards in favor of the other argument. That value is also what reduced_val returns for a range with no days in it, which has no best day. No day and profit can play this role, because whatever profit it held, a real day could do no better, and Combine would then keep the identity instead of the day. So the values are optionals: a (day, profit) pair for a real day, and std::nullopt, meaning "no day", as the identity:

// A (day, profit) pair, or nothing for a range with no days
using best_day = std::optional<std::pair<int, int>>;

constexpr auto better = [](const best_day& a, const best_day& b) -> best_day {
  if (!a) return b;
  if (!b) return a;
  return b->second > a->second ? b : a;
};

using best_dict = par::aug_treap_dict<int, best_day, better, std::nullopt>;

// Each day's entry: its profit, together with the day itself
auto with_day = [](const std::pair<int, int>& day_profit) -> std::pair<int, best_day> {
  return {day_profit.first, day_profit};
};

auto days = best_dict::from_sequence(par::map(week, with_day));
best_day best = days.reduced_val();                         // the pair (2, 30)
best_day best_late = days.get_range(3, 6).reduced_val();    // the pair (4, 30)

with_day turns each day's profit into its value, the pair (day, profit). When two days made the same profit, better keeps its left argument, which is the earlier day: days 2 and 4 both made 30, and the best day of the week is day 2. Swapping the arguments of better can therefore change its answer, so it is not commutative. That is fine, because values are always combined in key order, so Combine only needs to be associative.

Advanced Example: MCSS

The most the shop made over a run of consecutive days is the maximum contiguous subsequence sum (MCSS) of its profits, from MCSSLab. The best run of a range cannot be found from the best runs of its two halves alone, because it might cross the middle: a run ending at the left half's last day followed by a run starting at the right half's first day. So, as in the divide-and-conquer solution, each reduced value summarizes a range of days with four numbers:

• total, the range's total profit;
• prefix, the most made by a run starting at its first day;
• suffix, the most made by a run ending at its last day;
• best, the most made by any run.

The last three count the empty run, which makes 0, so they are never negative. Combine combines the summaries of two adjacent ranges, left then right, and its identity is the summary of no days at all, which is all zeros.

The stored values can stay plain profits, thanks to an optional fifth template parameter, Lift. It turns each stored value into a combined value before Combine sees it, and by default leaves values as they are. Here it turns each profit into the summary of a range holding just that day, so the dictionary is built from week directly, and augmented_value_type is summary, the type of Lift's results.

struct summary {
  int total, prefix, suffix, best;
};

constexpr auto combine = [](const summary& l, const summary& r) -> summary {
  return {.total = l.total + r.total,
          .prefix = std::max(l.prefix, l.total + r.prefix),
          .suffix = std::max(r.suffix, l.suffix + r.total),
          .best = std::max({l.best, r.best, l.suffix + r.prefix})};
};

// The summary of a range holding just one day
constexpr auto summarize = [](int profit) -> summary {
  int q = std::max(profit, 0);
  return {profit, q, q, q};
};

using runs_dict = par::aug_treap_dict<int, int, combine, summary{}, summarize>;

auto runs = runs_dict::from_sequence(week);
int best_run = runs.reduced_val().best;                         // 45: days 1 to 4
int best_late_run = runs.get_range(3, 6).reduced_val().best;    // 30: day 4

The best run of the week makes 45, from day 1 through day 4, despite the loss on day 3.