Treaps

Written by Johannes Kapfhammer.

Contents

Balanced Binary Search Tree
Rope
When not to use treaps

A treap (conjunction of the words tree and heap) is a binary search tree that uses randomization and the binary heap property to maintain balance with a high probability. It maintains a dynamic set of ordered keys and allows binary searches among these keys.

Treaps can be used for two use cases: a regular treap as a balanced binary search tree, or an implicit cartesian tree as rope data structure. This article covers both.

Balanced Binary Search Tree

Some of this text has been taken from this SOIminar article by Nicolas Camenisch.

Each node of a treap contains two values: A key (ordered using binary search tree properties) and a priority (ordered using heap properties). The heap order can either be maintained using a max heap or a min heap. In all following examples a max heap will be used.

The structure of a treap follows these rules:

The nodes in the left subtree of the root will have key values that are less than the key of the root. $\forall \texttt{x} \in \texttt{root.left}, \quad \texttt{x.key} < \texttt{root.key}$
The nodes in the right subtree of the root will have key values that are greater than the key of the root. $\forall \texttt{x} \in \texttt{root.right}, \quad \texttt{x.key} > \texttt{root.key}$
All priorities are unique.
The priority value of the root is greater than the priority values of its children. $\forall \texttt{x} \in \texttt{root.left} \cup \texttt{root.right}, \quad \texttt{x.priority} < \texttt{root.priority}$

These rules ensure that there is only one unique and valid structure for each possible set of keys and priorities.

Basic Treap

Below is a basic implementation of a heap, supporting only the operations insert, erase and contains.

Note that a std::multiset<T> or std::unordered_multiset<T> can serve the same functionality.

Treap with insert/erase/contains. (Expand)Copy

template <typename T, typename Rng=mt19937>
class treap {
  struct node {
    node(T const& x, Rng& rng) : x(x), y(rng()), l(nullptr), r(nullptr) {}
    T x;
    typename Rng::result_type y;
    unique_ptr<node> l, r;
    unique_ptr<node>& get_side(T x2) { return x2 < x ? l : r; }
    unique_ptr<node> const& get_side(T x2) const { return x2 < x ? l : r; }
  };
  using node_ptr = unique_ptr<node>;

  // precondition: all values of l are <= all the values of r
  static node_ptr merge(node_ptr l, node_ptr r) {
    if (!l) return r;
    if (!r) return l;
    if (l->y < r->y) {
      l->r = merge(move(l->r), move(r));
      return l;
    } else {
      r->l = merge(move(l), move(r->l));
      return r;
    }
  }

  // the first tree contains all values that are <x, the second all >=x
  static pair<node_ptr, node_ptr> split(node_ptr root, T const& x) {
    if (!root) return {};
    if (x < root->x) {
      node_ptr l;
      tie(l, root->l) = split(move(root->l), x);
      return {move(l), move(root)};
    } else {
      node_ptr r;
      tie(root->r, r) = split(move(root->r), x);
      return {move(root), move(r)};
    }
  }

  static node_ptr insert(node_ptr root, node_ptr val) {
    auto [l, r] = split(move(root), val->x);
    return merge(move(l), merge(move(val), move(r)));
  }

  static node_ptr erase(node_ptr root, T const& x) {
    if (!root) return root;
    if (root->x == x) return merge(move(root->l), move(root->r));
    node_ptr& sub = root->get_side(x);
    sub = erase(move(sub), x);
    return root;
  }

  static bool contains(node_ptr const& root, T const& x) {
    if (!root) return false;
    if (root->x == x) return true;
    return contains(root->get_side(x), x);
  }

  node_ptr root;
  mt19937 rng;

public:
  void insert(T value) { root = insert(move(root), make_unique<node>(value, rng)); }
  void erase(T value) { root = erase(move(root), value); }
  bool contains(T const& value) const { return contains(root, value); }
};

Accessing Elements by Order Index

To return the element at a given index, we need to keep track of the size of each subtree.

Note that policy based data structures can used for this purpose as well.

You can solve the task ORDERSET with this.

Treap with find_by_order/order_of_key (Expand)Copy

template <typename T, typename Rng=mt19937>
class treap {

  struct node {
    node(T const& x, Rng& rng) : x(x), y(rng()) {}
    T x;
    typename Rng::result_type y;
    unique_ptr<node> l=nullptr, r=nullptr;
    size_t cnt=1;
    unique_ptr<node>& get_side(T x2) { return x2 < x ? l : r; }
    unique_ptr<node> const& get_side(T x2) const { return x2 < x ? l : r; }

    static size_t size(unique_ptr<node> const& v) { return v ? v->cnt : 0; }
    void recompute() { cnt = size(l) + size(r) + 1; }
  };
  using node_ptr = unique_ptr<node>;

  static node_ptr merge(node_ptr l, node_ptr r) {
    if (!l) return r;
    if (!r) return l;
    if (l->y < r->y) {
      l->r = merge(move(l->r), move(r));
      l->recompute();
      return l;
    } else {
      r->l = merge(move(l), move(r->l));
      r->recompute();
      return r;
    }
  }

  static pair<node_ptr, node_ptr> split(node_ptr root, T const& x) {
    if (!root) return {};
    if (x < root->x) {
      node_ptr l;
      tie(l, root->l) = split(move(root->l), x);
      root->recompute();
      return {move(l), move(root)};
    } else {
      node_ptr r;
      tie(root->r, r) = split(move(root->r), x);
      root->recompute();
      return {move(root), move(r)};
    }
  }

  static node_ptr insert(node_ptr root, node_ptr val) {
    auto [l, r] = split(move(root), val->x);
    return merge(move(l), merge(move(val), move(r)));
  }

  static node_ptr erase(node_ptr root, T const& x) {
    if (!root) return root;
    if (x == root->x) {
      root = merge(move(root->l), move(root->r));
      if (root) root->recompute();
      return root;
    }
    node_ptr& sub = root->get_side(x);
    sub = erase(move(sub), x);
    root->recompute();
    return root;
  }

  static bool contains(node_ptr const& root, T const& x) {
    if (!root) return false;
    if (root->x == x) return true;
    return contains(root->get_side(x), x);
  }

  static node_ptr const& find_by_order(node_ptr const& root, size_t index) {
    assert(index < node::size(root));
    assert(root);
    auto left_size = node::size(root->l);
    if (index < left_size)
      return find_by_order(root->l, index);
    if (index > left_size)
      return find_by_order(root->r, index-left_size-1);
    return root;
  }

  static size_t order_of_key(node_ptr const& root, T const& x) {
    if (!root) return 0;
    if (x < root->x) return order_of_key(root->l, x);
    if (x > root->x) return order_of_key(root->r, x) + node::size(root->l) + 1;
    return node::size(root->l);
  }

  node_ptr root;
  mt19937 rng;

public:
  void insert(T value) { root = insert(move(root), make_unique<node>(value, rng)); }
  void erase(T value) { root = erase(move(root), value); }
  size_t size() const { return node::size(root); }
  T& find_by_order(size_t index) const { assert(index < size()); return find_by_order(root, index)->x; }
  size_t order_of_key(T const& x) const { return order_of_key(root, x); }
  bool contains(T const& value) const { return contains(root, value); }
};

Range Queries

Similar to Advanced Segment Trees, you can have arbitrary combiner functions.

Note that all functions we had so far (merge, split, insert, erase, contains, find_by_order, order_of_key) are identical. The only thing that needed to change was the representation of our node struct and the function recompute.

Below is a code that solves the problem TREAP.

Treap with arbitrary metadata (Expand)Copy

template <typename T>
struct metadata {
  T x, lo, hi;
  size_t cnt=1;
  T min_diff=numeric_limits<T>::max();

  static constexpr metadata neutral_element() { return {0, 0, 0, 0, 0}; }
};
template <typename T>
metadata<T> combine(T x, metadata<T> const& l, metadata<T> const& r) {
  size_t cnt = 1;
  T diff = numeric_limits<T>::max();
  T lo, hi;
  if (l.cnt) {
    cnt += l.cnt;
    diff = min({diff, l.min_diff, x - l.hi});
    lo = l.lo;
  } else {
    lo = x;
  }
  if (r.cnt) {
    cnt += r.cnt;
    diff = min({diff, r.min_diff, r.lo - x});
    hi = r.hi;
  } else {
    hi = x;
  }
  return {x, lo, hi, cnt, diff};
}

template <typename Metadata, typename Rng=mt19937>
class treap {
public:
  using T = decltype(declval<Metadata>().x);
private:
  struct node : Metadata {
    node(T const& x, Rng& rng) : Metadata(combine(x, Metadata::neutral_element(), Metadata::neutral_element())), y(rng()) {}

    typename Rng::result_type y;
    unique_ptr<node> l=nullptr, r=nullptr;

    unique_ptr<node>& get_side(T x2) { return x2 < this->x ? l : r; }
    unique_ptr<node> const& get_side(T x2) const { return x2 < this->x ? l : r; }

    static size_t size(unique_ptr<node> const& v) { return v ? v->cnt : 0; }
    void recompute() {
      static_cast<Metadata&>(*this) = combine(this->x,
                                              l ? static_cast<Metadata const&>(*l) : Metadata::neutral_element(),
                                              r ? static_cast<Metadata const&>(*r) : Metadata::neutral_element());
    }
  };
  using node_ptr = unique_ptr<node>;

  static node_ptr merge(node_ptr l, node_ptr r) {
    if (!l) return r;
    if (!r) return l;
    if (l->y < r->y) {
      l->r = merge(move(l->r), move(r));
      l->recompute();
      return l;
    } else {
      r->l = merge(move(l), move(r->l));
      r->recompute();
      return r;
    }
  }

  static pair<node_ptr, node_ptr> split(node_ptr root, T const& x) {
    if (!root) return {};
    if (x < root->x) {
      node_ptr l;
      tie(l, root->l) = split(move(root->l), x);
      root->recompute();
      return {move(l), move(root)};
    } else {
      node_ptr r;
      tie(root->r, r) = split(move(root->r), x);
      root->recompute();
      return {move(root), move(r)};
    }
  }

  static node_ptr insert(node_ptr root, node_ptr val) {
    auto [l, r] = split(move(root), val->x);
    return merge(move(l), merge(move(val), move(r)));
  }

  static node_ptr erase(node_ptr root, T const& x) {
    if (!root) return root;
    if (x == root->x) {
      root = merge(move(root->l), move(root->r));
      if (root) root->recompute();
      return root;
    }
    node_ptr& sub = root->get_side(x);
    sub = erase(move(sub), x);
    root->recompute();
    return root;
  }

  static bool contains(node_ptr const& root, T const& x) {
    if (!root) return false;
    if (root->x == x) return true;
    return contains(root->get_side(x), x);
  }

  static node_ptr const& find_by_order(node_ptr const& root, size_t index) {
    assert(index < node::size(root));
    assert(root);
    auto left_size = node::size(root->l);
    if (index < left_size)
      return find_by_order(root->l, index);
    if (index > left_size)
      return find_by_order(root->r, index-left_size-1);
    return root;
  }

  static size_t order_of_key(node_ptr const& root, T const& x) {
    if (!root) return 0;
    if (x < root->x) return order_of_key(root->l, x);
    if (x > root->x) return order_of_key(root->r, x) + node::size(root->l) + 1;
    return node::size(root->l);
  }

  Metadata query(node_ptr const& root, ssize_t l, ssize_t r) const {
    if (!root || r <= 0 || l >= (ssize_t)node::size(root)) return Metadata::neutral_element();
    if (l <= 0 && node::size(root) <= r) return *root;
    ssize_t left_size = node::size(root->l);
    auto ql = [&]() { return query(root->l, l, r); };
    auto qr = [&]() { return query(root->r, l - left_size - 1, r - left_size - 1); };
    if (r <= left_size) return ql();
    if (l >= left_size+1) return qr();
    return combine(root->x, ql(), qr());
  }

  node_ptr root;
  mt19937 rng;

public:
  void insert(T value) { root = insert(move(root), make_unique<node>(value, rng)); }
  void erase(T value) { root = erase(move(root), value); }
  size_t size() const { return node::size(root); }
  T& find_by_order(size_t index) const { assert(index < size()); return find_by_order(root, index)->x; }
  size_t order_of_key(T const& x) const { return order_of_key(root, x); }
  bool contains(T const& value) const { return contains(root, value); }
  Metadata query(size_t l, size_t r) const { assert(l <= r); assert(r <= size()); return query(root, l, r); }
};

It’s possible to extend this idea to lazy updates. We will see more of that below.

Rope

This text is taken from https://cp-algorithms.com/data_structures/treap.html.

Implicit treap is a simple modification of the regular treap which is a very powerful data structure. In fact, implicit treap can be considered as an array with the following procedures implemented (all in $O(\log n)$ in the online mode):

Inserting an element in the array in any location
Removal of an arbitrary element
Finding sum, minimum / maximum element etc. on an arbitrary interval
Addition, painting on an arbitrary interval
Reversing elements on an arbitrary interval

The idea is that the keys should be indices of the elements in the array. But we will not store these values explicitly (otherwise, for example, inserting an element would cause changes of the key in $O(n)$ nodes of the tree).

Note that the key of a node is the number of nodes less than it (such nodes can be present not only in its left subtree but also in left subtrees of its ancestors). More specifically, the implicit key for some node T is the number of vertices $cnt(T\to L)$ in the left subtree of this node plus similar values $cnt(P\to L)+1$ for each ancestor P of the node T, if T is in the right subtree of P.

Now it’s clear how to calculate the implicit key of current node quickly. Since in all operations we arrive to any node by descending in the tree, we can just accumulate this sum and pass it to the function. If we go to the left subtree, the accumulated sum does not change, if we go to the right subtree it increases by $cnt(T\to L)+1$ .

Basic Implicit Treap

Below is an implementation for the task AROPE.

basic implicit treap (Expand)Copy

mt19937 rng;

template <typename T>
class implicit_treap {
  struct node {
    node(T const& x) : x(x), y(rng()) {}
    T x;
    decltype(rng)::result_type y;
    unique_ptr<node> l=nullptr, r=nullptr;
    size_t cnt = 1;

    static size_t size(unique_ptr<node> const& v) { return v ? v->cnt : 0; }
    void recompute() { cnt = size(l) + size(r) + 1; }
  };
  using node_ptr = unique_ptr<node>;

  static node_ptr merge(node_ptr l, node_ptr r) {
    if (!l) return r;
    if (!r) return l;
    if (l->y < r->y) {
      l->r = merge(move(l->r), move(r));
      l->recompute();
      return l;
    } else {
      r->l = merge(move(l), move(r->l));
      r->recompute();
      return r;
    }
  }

  static pair<node_ptr, node_ptr> split_at(node_ptr root, size_t at) {
    if (!root) return {};
    size_t left_size = node::size(root->l);
    if (at <= left_size) {
      node_ptr l;
      tie(l, root->l) = split_at(move(root->l), at);
      root->recompute();
      return {move(l), move(root)};
    } else {
      node_ptr r;
      tie(root->r, r) = split_at(move(root->r), at - left_size - 1);
      root->recompute();
      return {move(root), move(r)};
    }
  }

  static node_ptr const& find_by_index(node_ptr const& root, size_t index) {
    assert(index < node::size(root));
    assert(root);
    auto left_size = node::size(root->l);
    if (index < left_size) return find_by_index(root->l, index);
    if (index > left_size) return find_by_index(root->r, index-left_size-1);
    return root;
  }

  node_ptr root;
  implicit_treap(node_ptr root) : root(move(root)) {}

public:
  implicit_treap() : root(nullptr) {}

  size_t size() const { return node::size(root); }
  void append(implicit_treap o) { root = merge(move(root), move(o.root)); }
  void push_back(T value) { append({ make_unique<node>(value) }); }
  void insert(size_t i, implicit_treap t) {
    auto [l, r] = split_at(move(root), i);
    root = merge(merge(move(l), move(t.root)), move(r));
  }
  implicit_treap cut(size_t l, size_t r) {
    assert(l <= r && r <= size());
    auto [a, bc] = split_at(move(root), l);
    auto [b, c] = split_at(move(bc), r - l);
    root = merge(move(a), move(c));
    return {move(b)};
  }
  T const& operator[](size_t i) const {
    assert(i < size());
    return find_by_index(root, i)->x;
  }
};

Range Queries

As with regular treaps, it’s easy to do range queries. The code for the query is exactly the same as before, so the code is not shown again. Below is code shown without Metadata struct, just inplace.

implicit treap with ``query`` function (Expand)Copy

mt19937 rng;

template <typename T>
class implicit_treap {
  struct node {
    node(T const& x) : x(x), xmax(x), y(rng()) {}
    T x, xmax;
    decltype(rng)::result_type y;
    unique_ptr<node> l=nullptr, r=nullptr;
    size_t cnt = 1;
    unique_ptr<node>& get_side(T x2) { return x2 < x ? l : r; }
    unique_ptr<node> const& get_side(T x2) const { return x2 < x ? l : r; }

    static size_t size(unique_ptr<node> const& v) { return v ? v->cnt : 0; }
    void recompute() {
      cnt = size(l) + size(r) + 1;
      xmax = x;
      if (l) xmax = max(xmax, l->xmax);
      if (r) xmax = max(xmax, r->xmax);
    }
  };
  using node_ptr = unique_ptr<node>;

  static node_ptr merge(node_ptr l, node_ptr r) {
    if (!l) return r;
    if (!r) return l;
    if (l->y < r->y) {
      l->r = merge(move(l->r), move(r));
      l->recompute();
      return l;
    } else {
      r->l = merge(move(l), move(r->l));
      r->recompute();
      return r;
    }
  }

  static pair<node_ptr, node_ptr> split_at(node_ptr root, size_t at) {
    if (!root) return {};
    size_t left_size = node::size(root->l);
    if (at <= left_size) {
      node_ptr l;
      tie(l, root->l) = split_at(move(root->l), at);
      root->recompute();
      return {move(l), move(root)};
    } else {
      node_ptr r;
      tie(root->r, r) = split_at(move(root->r), at - left_size - 1);
      root->recompute();
      return {move(root), move(r)};
    }
  }

  static node_ptr const& find_by_index(node_ptr const& root, size_t index) {
    assert(index < node::size(root));
    assert(root);
    auto left_size = node::size(root->l);
    if (index < left_size) return find_by_index(root->l, index);
    if (index > left_size) return find_by_index(root->r, index-left_size-1);
    return root;
  }

  node_ptr root;
  implicit_treap(node_ptr root) : root(move(root)) {}

  int query(node_ptr const& root, ssize_t l, ssize_t r) const {
    if (!root || r <= 0 || l >= (ssize_t)node::size(root)) return numeric_limits<int>::min();
    if (l <= 0 && node::size(root) <= r) return root->xmax;
    ssize_t left_size = node::size(root->l);
    auto ql = [&]() { return query(root->l, l, r); };
    auto qr = [&]() { return query(root->r, l - left_size - 1, r - left_size - 1); };
    if (r <= left_size) return ql();
    if (l >= left_size+1) return qr();
    return max({root->x, ql(), qr()});
  }

public:
  implicit_treap() : root(nullptr) {}

  size_t size() const { return node::size(root); }
  void append(implicit_treap o) { root = merge(move(root), move(o.root)); }
  void push_back(T value) { append({ make_unique<node>(value) }); }
  void insert(size_t i, implicit_treap t) {
    node_ptr l, r; tie(l, r) = split_at(move(root), i);
    root = merge(merge(move(l), move(t.root)), move(r));
  }
  void insert(size_t i, T value) {
    insert(i, implicit_treap(make_unique<node>(value)));
  }
  T const& operator[](size_t i) const {
    assert(i < size());
    return find_by_index(root, i)->x;
  }
  int query(size_t l, size_t r) const { assert(l <= r); assert(r <= size()); return query(root, l, r); }
};

Example problem: QMAX3VN.

Lazy Updates

Here, again, one can do arbitrary operations. Below is the implementation of reversing a range, which can be used to solve the task AROPE3.

The idea is exactly the same as for a lazy segment tree. We implement apply, combine and neutral_element for the specific task, have helper functions apply and propagate. The only change in the query functions was to insert propagate when appropriate.

implicit treap with a lazy ``reverse`` (Expand)Copy

mt19937 rng;

struct lazy_reverse {
  bool rev;
  template <typename Node> static void apply(lazy_reverse l, Node& n) { if (l.rev) swap(n.l, n.r); }
  static lazy_reverse combine(lazy_reverse a, lazy_reverse b) { return {a.rev != b.rev}; }
  static lazy_reverse neutral_element() { return {false}; }
};

template <typename T, typename Lazy>
class implicit_treap {
  struct node {
    node(T const& x) : x(x), y(rng()) {}
    T x;
    Lazy lazy=Lazy::neutral_element();
    decltype(rng)::result_type y;
    unique_ptr<node> l=nullptr, r=nullptr;
    size_t cnt = 1;

    static size_t size(unique_ptr<node> const& v) { return v ? v->cnt : 0; }
    void recompute() { cnt = size(l) + size(r) + 1; }
    void apply(Lazy update) {
      Lazy::apply(update, *this);
      lazy = Lazy::combine(update, lazy);
    }
    void propagate() {
      if (l) l->apply(lazy);
      if (r) r->apply(lazy);
      lazy = Lazy::neutral_element();
    }
  };
  using node_ptr = unique_ptr<node>;

  static node_ptr merge(node_ptr l, node_ptr r) {
    if (!l) return r;
    if (!r) return l;

    l->propagate();
    r->propagate();

    if (l->y < r->y) {
      l->r = merge(move(l->r), move(r));
      l->recompute();
      return l;
    } else {
      r->l = merge(move(l), move(r->l));
      r->recompute();
      return r;
    }
  }

  static pair<node_ptr, node_ptr> split_at(node_ptr root, size_t at) {
    if (!root) return {};
    root->propagate();
    size_t left_size = node::size(root->l);
    if (at <= left_size) {
      node_ptr l;
      tie(l, root->l) = split_at(move(root->l), at);
      root->recompute();
      return {move(l), move(root)};
    } else {
      node_ptr r;
      tie(root->r, r) = split_at(move(root->r), at - left_size - 1);
      root->recompute();
      return {move(root), move(r)};
    }
  }

  static node_ptr const& find_by_index(node_ptr const& root, size_t index) {
    assert(index < node::size(root));
    assert(root);
    root->propagate();
    auto left_size = node::size(root->l);
    if (index < left_size) return find_by_index(root->l, index);
    if (index > left_size) return find_by_index(root->r, index-left_size-1);
    return root;
  }

  node_ptr root;
  implicit_treap(node_ptr root) : root(move(root)) {}

public:
  implicit_treap() : root(nullptr) {}

  void reverse() { if (root) root->apply({true}); }
  size_t size() const { return node::size(root); }
  void append(implicit_treap o) { root = merge(move(root), move(o.root)); }
  void push_back(T value) { append({ make_unique<node>(value) }); }
  void insert(size_t i, implicit_treap t) {
    auto [l, r] = split_at(move(root), i);
    root = merge(merge(move(l), move(t.root)), move(r));
  }
  implicit_treap cut(size_t l, size_t r) {
    assert(l <= r && r <= size());
    auto [a, bc] = split_at(move(root), l);
    auto [b, c] = split_at(move(bc), r - l);
    root = merge(move(a), move(c));
    return {move(b)};
  }
  T const& operator[](size_t i) const {
    assert(i < size());
    return find_by_index(root, i)->x;
  }
};

When not to use treaps

Treaps (or any balanced binary search tree for that matter) are very powerful data structures. However, it’s not always wise to implement them during a contest. Before coding them, please double-check that you really need them.

Can you modify the queries such that a std::set<T> is sufficient?
Can it be solved with policy based data structures?
Can you do coordinate-compression such that a segment tree is sufficient?
Is a sparse segment tree enough?
Can I get points in other subtasks? (Then rather go for them.)

Sparse segment trees are segment trees where instead of storing the nodes in a heap, each node has a left and a right pointer (like in a treap). The advantage of sparse segment trees over treaps is that you don’t need any kind of rebalancing. In theory, segment trees are limited to storing integers, however for most tasks this is not a big issue.