AIOJ

Prior knowledge: Naive binary search tree, Heap basics.

Introduction

A Treap is a weakly balanced binary search tree.

In addition to the value ( $\textit{val}$ ) maintained by each Treap node, it has an additional random priority ( $\textit{priority}$ ). The values satisfy the binary search tree property, while the priorities satisfy the heap property (either a min-heap or a max-heap).

The binary search tree property means:

The values ( $\textit{val}$ ) of all nodes in the left subtree are smaller than the value of the parent.
The values ( $\textit{val}$ ) of all nodes in the right subtree are larger than the value of the parent.

The heap property is:

The priority ( $\textit{priority}$ ) of a child is greater or smaller than that of its parent, depending on whether it is a min-heap or a max-heap.

It is easy to see that if the same value were used for both properties, combining these two data structures would produce a chain. Therefore, on top of the search tree, we introduce a heap value $\textit{priority}$ . We maintain the search tree property for $\textit{val}$ and the heap property for $\textit{priority}$ . The value $\textit{priority}$ is assigned randomly.

The following figure is an example of a Treap (a min-heap is used here, so the root has the smallest priority).

An example of a Treap

Why, then, do we go to such lengths to make this data structure satisfy both tree and heap properties, and assign the heap values randomly?

To understand this, we first need to understand the problem with a naive binary search tree. When inserting a new node into a naive search tree, we recursively start at the root. If the new node is smaller than the current node, we recurse to the left; otherwise, we recurse to the right.

When the current node is found to have no child, the new node becomes its left or right child according to the relative values.

If the values of inserted nodes are random (in other words, if they are inserted in random order), the height of the naive search tree is small (close to $\log n$ , where $n$ is the number of nodes), and each level has many nodes, so its shape is very “fat”. The Treap above is an example. Thus, the complexity of any operation is approximately $O(\log n)$ in this case.

However, this is the complexity in the random case. If we insert nodes into a naive search tree in the highly ordered sequence below:

1 2 3 4 5

the tree degenerates into a chain, becoming very “thin” (each inserted node is larger than the preceding ones, so all of them are placed in the right subtree):

An example of degeneration into a chain

It is not difficult to see that the complexity of a query also changes from $O(\log n)$ to $O(n)$ .

To solve this problem and reach a relatively “balanced” state, a Treap maintains random priorities satisfying the heap property and “shuffles” the insertion order of nodes. This gives the binary search tree its ideal complexity and avoids degeneration into a chain.

Proof of Treap complexity

Since the complexity of various Treap operations is related to the depth of the node being operated on, we first prove that the expected depth of every node is $O(\log n)$ .

Notation

For convenience, we use the following notation:

$n$ is the number of nodes.
A property of a Treap node that satisfies the binary search tree property is called its value, while the property that satisfies the heap property (and is therefore random) is called its priority. We may assume that priorities satisfy the min-heap property.
$x_k$ denotes the node with the $k$ -th smallest value.
$X_{i,j}$ denotes the set $\{x_i,x_{i+1},\cdots,x_{j-1},x_j\}$ , namely, the set of nodes ranked from $i$ through $j$ in ascending order of value.
$\operatorname{dep}(x)$ denotes the depth of node $x$ . The depth of the root is defined to be $0$ .
$Y_{i,j}$ is an indicator random variable. When $x_i$ is an ancestor of $x_j$ , its value is $1$ ; otherwise, it is $0$ . In particular, $Y_{i,i}=0$ .
$\Pr(A)$ denotes the probability that event $A$ occurs.

Proof of expected node depth

Since the depth of node $x_i$ equals the number of its ancestors, we have

\operatorname{dep}(x_i)=\sum_{k=1}^nY_{k,i}.

By linearity of expectation,

E(\operatorname{dep}(x_i))=E\left(\sum_{k=1}^nY_{k,i}\right)=\sum_{k=1}^nE(Y_{k,i}).

Since $Y_{k,i}$ is an indicator random variable, its expectation equals the probability that it is $1$ . Therefore,

E(\operatorname{dep}(x_i))=\sum_{k=1}^n\Pr(Y_{k,i}=1).

We first prove the lemma: $Y_{i,j}=1$ if and only if the priority of $x_i$ is the smallest in $X_{i,j}$ .

Proof of the lemma

Consider the cases for $x_i$ and $x_j$ .

If $x_i$ is the root: because priorities satisfy the min-heap property, $x_i$ has the smallest priority, and for every $x_j$ , $x_i$ is an ancestor of $x_j$ .
If $x_j$ is the root: similarly, $x_j$ has the smallest priority, so $x_i$ is not the node with the smallest priority in $X_{i,j}$ ; at the same time, $x_i$ is not an ancestor of $x_j$ .
If $x_i$ and $x_j$ are in the two subtrees of the root, one on each side, then the root $r\in X_{i,j}$ . Therefore, the priority of $x_i$ cannot be the smallest in $X_{i,j}$ , because the root has a smaller priority. At the same time, since $x_i$ and $x_j$ belong to different subtrees, $x_i$ is not an ancestor of $x_j$ .
If $x_i$ and $x_j$ are in the same subtree of the root, we can take that subtree out as a new Treap and recursively apply the proof above.

By the lemma, the expected depth can be rewritten as

E(\operatorname{dep}(x_i))=\sum_{k=1}^n\Pr(x_k=\min X_{i,k}\land k\neq i).

Since node priorities are random, we assume that every node in $X_{i,j}$ is equally likely to have the smallest priority. Hence,

\begin{aligned} E(\operatorname{dep}(x_i))&=\sum_{k=1}^n\Pr(x_k=\min X_{i,k}\land k\neq i)\\ &=\sum_{k=1}^{n}\Pr(x_k=\min X_{i,k})-1\\ &=\sum_{k=1}^n\dfrac{1}{|i-k|+1}-1\\ &=\sum_{k=1}^{i-1}\dfrac{1}{i-k+1}+\sum_{k=i+1}^n\dfrac{1}{k-i+1}\\ &=\sum_{j=2}^i\dfrac 1j+\sum_{j=2}^{n-i+1}\dfrac 1j\\ &\le 2\sum_{j=2}^n\dfrac 1j < 2\sum_{j=2}^n\int_{j-1}^j\dfrac 1x\mathrm dx\\ &=2\int_1^n\dfrac 1x\mathrm dx=2\ln n=O(\log n). \end{aligned}

Therefore, the expected depth of every node is $O(\log n)$ .

The complexity of operations in a naive binary search tree is $O(h)$ , and maintaining the heap property in a Treap also has complexity $O(h)$ . Therefore, the expected complexity of every Treap operation is $O(\log n)$ .

Intuitive understanding of expected complexity

First, we need to recognize that a node's $\textit{priority}$ attribute is directly related to the level where it is located. Recall the heap property:

The value ( $\textit{priority}$ ) of a child is greater or smaller than that of its parent, depending on whether it is a min-heap or a max-heap.

We find that nodes at lower levels, such as the root of the entire tree, also have a smaller $\textit{priority}$ attribute (in a min-heap). Moreover, in a naive search tree, nodes inserted earlier are more likely to be at relatively low levels. We can associate the $\textit{priority}$ attribute with the insertion order; this makes it clear why a Treap can shuffle the insertion order of nodes through $\textit{priority}$ .

When inserting a new node into a Treap, both the tree and heap properties must be maintained. The search tree property can be maintained during insertion, while the heap property can be maintained in two ways: by rotations or by split and merge. Treaps using these two methods are called rotational Treaps and non-rotational Treaps, respectively.

Rotational Treap

A rotational Treap maintains balance through rotations. Similar to rotations in an AVL tree, it has left rotation and right rotation. In other words, it balances the Treap according to heap priorities while preserving the binary search tree property.

For ordinary balanced-tree problems, the rotational Treap has one of the smallest constants among all balanced trees.

The code in the following explanation implements a rotational Treap with pointers; a complete array-based implementation is attached at the end of the article.

Info

In the code, rank represents the priority ( $\textit{priority}$ ) discussed above, and it satisfies the min-heap property.

Node structure

struct Node {
  Node *ch[2];  // addresses of the two child nodes
  int val, rank;
  int rep_cnt;  // number of occurrences of the current value (val)
  int siz;      // size of the subtree rooted at the current node

  Node(int val) : val(val), rep_cnt(1), siz(1) {
    ch[0] = ch[1] = nullptr;
    rank = rand();
    // Note that rank is assigned randomly during initialization
  }

  void upd_siz() {
    // Recalculate siz after a rotation or deletion
    siz = rep_cnt;
    if (ch[0] != nullptr) siz += ch[0]->siz;
    if (ch[1] != nullptr) siz += ch[1]->siz;
  }
};

Rotation

Rotation is a very important Treap operation. It is mainly used to adjust the levels of different nodes while preserving the Treap's tree property, thereby maintaining the heap property.

It may not be particularly easy to distinguish left and right rotations. The following are two relatively obvious features:

The meaning of a rotation is:

Without affecting the search tree property, make the subtree opposite to the rotation direction the root (for example, a left rotation makes the right subtree the root).
Without affecting the properties, after the rotation the child in the same direction as the rotation becomes the original root (for example, after a left rotation, the left child is the root before the rotation).

Left and right rotations are inverse operations, as shown in the following figure.

Rotation

enum rot_type { LF = 1, RT = 0 };

void _rotate(Node *&cur,
             rot_type dir) {  // dir represents the rotation direction: 0 is right and 1 is left
  // Note that cur is passed by reference, so changing it also changes
  // cur，the variable. If this cur is a child of another tree, following ch
  // to find it will also lead here

  // The following code describes the left-rotation case
  Node *tmp = cur->ch[dir];  // make C the root，
                             // tmp here
                             // is a temporary node pointer pointing to the node that becomes the new root

  /* Left rotation: make the right child the root
   *         A                 C
   *        / \               / \
   *       B  C    ---->     A   E
   *         / \            / \
   *        D   E          B   D
   */
  cur->ch[dir] = tmp->ch[!dir];    // make A's right child D
  tmp->ch[!dir] = cur;             // make C's left child A
  cur->upd_siz(), tmp->upd_siz();  // update size information
  cur = tmp;  // finally assign the variable temporarily storing tree C to the current root (note that cur is a reference)
}

Insertion

This is similar to insertion into an ordinary binary search tree, but rotations are needed during insertion to maintain the heap property of priorities.

void _insert(Node *&cur, int val) {
  if (cur == nullptr) {
    // create a new node directly if this node does not exist
    cur = new Node(val);
    return;
  } else if (val == cur->val) {
    // if a node with the same value exists, increase the duplicate count
    cur->rep_cnt++;
    cur->siz++;
  } else if (val < cur->val) {
    // maintain the search tree property: insert to the left if val is smaller than the current node, and to the right otherwise
    _insert(cur->ch[0], val);
    if (cur->ch[0]->rank < cur->rank) {
      // in a min-heap, the upper node's priority must be smaller
      // because the newly inserted left child is smaller than its parent, make the left child the parent
      _rotate(cur, RT);  // as described above, bring the left child up with a right rotation
    }
    cur->upd_siz();  // the size changes after insertion, so update it
  } else {
    _insert(cur->ch[1], val);
    if (cur->ch[1]->rank < cur->rank) {
      _rotate(cur, LF);
    }
    cur->upd_siz();
  }
}

Deletion

The main task is to distinguish cases, with a different method for each case. The size of the tree changes after deletion, so remember to update it. In addition, if the node to be deleted has both a left and a right subtree, we need to decide which one becomes the parent after deletion (the node with the smaller rank must stay above).

void _del(Node *&cur, int val) {
  if (val > cur->val) {
    _del(cur->ch[1], val);
    // the larger value is in the right subtree, and vice versa
    cur->upd_siz();
  } else if (val < cur->val) {
    _del(cur->ch[0], val);
    cur->upd_siz();
  } else {
    if (cur->rep_cnt > 1) {
      // if the node to delete is duplicated, simply decrease the duplicate count
      cur->rep_cnt--, cur->siz--;
      return;
    }
    uint8_t state = 0;
    state |= (cur->ch[0] != nullptr);
    state |= ((cur->ch[1] != nullptr) << 1);
    // 00: neither; 01: left only; 10: right only; 11: both
    Node *tmp = cur;
    switch (state) {
      case 0:
        delete cur;
        cur = nullptr;
        // with no child nodes, delete this node directly
        break;
      case 1:  // has a left child but no right child
        cur = tmp->ch[0];
        // make the root the left child, then delete the original root; note that tmp is copied from cur
        // while cur is a reference
        delete tmp;
        break;
      case 2:  // has a right child but no left child
        cur = tmp->ch[1];
        delete tmp;
        break;
      case 3:
        rot_type dir = cur->ch[0]->rank < cur->ch[1]->rank
                           ? RT
                           : LF;  // dir is the child with the smaller rank
        _rotate(cur, dir);  // this rotation brings the child with smaller priority up; rt is 0,
                            // and lf is 1, exactly opposite to the actual subtree indices
        _del(
            cur->ch[!dir],
            val);  // after rotation, the original root is on the rotation-direction side, so continue
                   // deleting that original root
                   // if the node to delete is at an upper level of the entire tree, these
                   // rotations keep moving it down until it has no subtree (or only one), then delete it.
        cur->upd_siz();
        // deletion changes the size
        break;
    }
  }
}

Querying the rank by value

Operation meaning: query the rank of the value val in the subtree rooted at cur (the number of nodes in this subtree smaller than val + 1).

int _query_rank(Node *cur, int val) {
  int less_siz = cur->ch[0] == nullptr ? 0 : cur->ch[0]->siz;
  // number of nodes in this tree smaller than val
  if (val == cur->val)
    // if this node is the node being queried
    return less_siz + 1;
  else if (val < cur->val) {
    if (cur->ch[0] != nullptr)
      return _query_rank(cur->ch[0], val);
    else
      return 1;  // if the left subtree is empty, val is smaller than the minimum node
  } else {
    if (cur->ch[1] != nullptr)
      // if the queried value is larger than this node, this node and its left subtree are certainly smaller than the queried value
      // add these two quantities to the result of searching to the right
      // (the rank of val in the subtree rooted at the right child)
      return less_siz + cur->rep_cnt + _query_rank(cur->ch[1], val);
    else
      return cur->siz + 1;
    // without a right subtree, the whole tree + 1 is equivalent to less_siz + cur->rep_cnt + 1
  }
}

Querying the value by rank

To query a value by rank, we first need to know which part of the tree contains the node being queried:

The following table gives one way to determine this:

Left subtree	Root/current node	Right subtree
Rank ≤ size of the left subtree	Rank > size of the left subtree and ≤ size of the left subtree + the number of duplicates of the root node	Rank > size of the left subtree + the number of duplicates of the root node

If the node is in the right subtree, note that the original rank needs to be adjusted during recursion. Recursing is equivalent to querying the value with this rank in the right subtree; to convert the rank to one based on the right subtree, subtract the size of the left subtree and the number of duplicates of the root node from the original rank.

Imagine all nodes as a sorted array, or a number line (as follows),

1 -> |nodes in the left subtree|root node|nodes in the right subtree| -> n
                               ^
                               queried rank
                         ⬇converted to a rank based on the right subtree
1 -> |nodes in the right subtree| -> n
       ^
       queried rank

The conversion is simply to subtract the size of the left subtree and the number of duplicates of the root node from the rank.

int _query_val(Node *cur, int rank) {
  // query the value of the node with rank rank in the tree
  int less_siz = cur->ch[0] == nullptr ? 0 : cur->ch[0]->siz;
  // less siz is the size of the left subtree
  if (rank <= less_siz)
    return _query_val(cur->ch[0], rank);
  else if (rank <= less_siz + cur->rep_cnt)
    return cur->val;
  else
    return _query_val(cur->ch[1], rank - less_siz - cur->rep_cnt);  // see above
}

Querying the first node smaller than val

Note that a class-wide global variable, q_prev_tmp, is used here.

This value is changed only when val is greater than the current node's value, so returning this variable returns the last value of a node that was smaller than val and after which the values became smaller.

int _query_prev(Node *cur, int val) {
  if (val <= cur->val) {
    // still greater than or equal to val, so search the left subtree
    if (cur->ch[0] != nullptr) return _query_prev(cur->ch[0], val);
  } else {
    // q_prev_tmp is updated only when entering this else branch
    q_prev_tmp = cur->val;
    // the current node is smaller than val, but it is not known whether it is the largest, so continue searching in the right subtree
    if (cur->ch[1] != nullptr) _query_prev(cur->ch[1], val);
    // the following recursion may not change q_prev_tmp
    // so return this value directly; in any case, what is returned is the cur->val from the last entry into this else branch
    // cur->val
    return q_prev_tmp;
  }
  return NIL;
}

Querying the first node larger than val

This is very similar to the preceding operation, except that the greater-than and less-than signs are exchanged.

int _query_nex(Node *cur, int val) {
  if (val >= cur->val) {
    if (cur->ch[1] != nullptr) return _query_nex(cur->ch[1], val);
  } else {
    q_nex_tmp = cur->val;
    if (cur->ch[0] != nullptr) _query_nex(cur->ch[0], val);
    return q_nex_tmp;
  }
  return NIL;
}

Non-rotational Treap

The operations of a non-rotational Treap naturally support maintaining sequences and persistence.

A non-rotational Treap is also called a split-and-merge Treap. It has only two core operations: split and merge. Through these two operations, many other operations can be implemented more conveniently than with a rotational Treap. We introduce the two operations one by one below.

Note

An explanation of non-rotational Treaps should mention FHQ-Treap (by Fan Haoqiang), a non-rotational Treap that supports persistence and interval operations. For more information, see the PPT Fan Haoqiang Discusses Data Structures.

Split

Split by value

The split process takes two parameters: the root pointer $\textit{cur}$ and the key value $\textit{key}$ . It splits the Treap pointed to by the root pointer into two Treaps: every node in the first has value ( $\textit{val}$ ) at most $\textit{key}$ , and every node in the second has value greater than $\textit{key}$ .

The process first checks whether $\textit{key}$ is smaller than the value of $\textit{cur}$ . If so, $\textit{cur}$ and its entire right subtree are greater than $\textit{key}$ and belong to the second Treap. Some nodes in the left subtree may also have values greater than $\textit{key}$ , so we continue splitting recursively in the left subtree. We make the part of the left subtree whose values are greater than $\textit{key}$ the left subtree of $\textit{cur}$ ; then every node in the entire tree rooted at $\textit{cur}$ is greater than $\textit{key}$ .

Conversely, if $\textit{key}$ is greater than or equal to the value of $\textit{cur}$ , then the entire left subtree of $\textit{cur}$ and $\textit{key}$ itself are at most $\textit{cur}$ and belong to the first split Treap. Some of the right subtree of $\textit{key}$ may also be at most $\textit{key}$ , so we continue splitting the right subtree recursively. We make the part at most $\textit{cur}$ the right subtree of $\textit{cur}$ ; then every node in the entire tree rooted at $\textit{key}$ is at most undefined.

The following figure shows splitting by value when the value of $\textit{cur}$ is at most $\textit{key}$ .¹

Split by value

pair<Node *, Node *> split(Node *cur, int key) {
  if (cur == nullptr) return {nullptr, nullptr};
  if (cur->val <= key) {
    // cur and its left subtree definitely belong to the first split tree
    auto temp = split(cur->ch[1], key);
    // but part of its right subtree may also be smaller than key
    cur->ch[1] = temp.first;
    // take the part smaller than key out as cur's right subtree, so all of cur is smaller
    // than key. The remaining right subtree becomes the second split Treap
    cur->upd_siz();
    // the size of the tree changes after splitting, so update it
    return {cur, temp.second};
  } else {
    // same as above
    auto temp = split(cur->ch[0], key);
    cur->ch[0] = temp.second;
    cur->upd_siz();
    return {temp.first, cur};
  }
}

Split by rank

Compared with splitting by value, this operation is more like querying a value by rank in a rotational Treap (the rank of a node is the number of nodes in the tree with values smaller than this node $+ 1$ ).

This function takes two parameters, the node pointer $\textit{cur}$ and the rank $\textit{rk}$ , and returns three split Treaps.

In the first Treap, every node has rank smaller than $\textit{rk}$ ; in the second, the rank equals $\textit{rk}$ , and the second Treap contains only one node (multiple equal nodes are impossible; if they existed, the Node structure's cnt would be increased); the third has a greater rank.

The key to this operation is determining which part of the tree contains the node whose rank equals $\textit{cur}$ ; this is also the important part of the query-by-rank operation for a rotational Treap, which was explained in detail above, so it will not be discussed further here.

The recursive part of this operation is also very similar to splitting by value, so it is omitted here.

tuple<Node *, Node *, Node *> split_by_rk(Node *cur, int rk) {
  if (cur == nullptr) return {nullptr, nullptr, nullptr};
  int ls_siz = cur->ch[0] == nullptr ? 0 : cur->ch[0]->siz;
  if (rk <= ls_siz) {
    // the node whose rank equals cur's is in the left subtree
    Node *l, *mid, *r;
    tie(l, mid, r) = split_by_rk(cur->ch[0], rk);
    cur->ch[0] = r;  // every node in the third returned Treap has rank greater than rk
    // after cur's left subtree is set to r, every node in cur has rank greater than rk
    cur->upd_siz();
    return {l, mid, cur};
  } else if (rk <= ls_siz + cur->cnt) {
    // the node whose rank equals cur's is the current node
    Node *lt = cur->ch[0];
    Node *rt = cur->ch[1];
    cur->ch[0] = cur->ch[1] = nullptr;
    // the second split Treap contains only one node, so set its subtrees to empty
    return {lt, cur, rt};
  } else {
    // the node whose rank equals cur's is in the right subtree
    // the recursive process is the same as above
    Node *l, *mid, *r;
    tie(l, mid, r) = split_by_rk(cur->ch[1], rk - ls_siz - cur->cnt);
    cur->ch[1] = l;
    cur->upd_siz();
    return {cur, mid, r};
  }
}

Merge

The merge process takes two parameters: the root pointer $\textit{u}$ of the left Treap and the root pointer $\textit{v}$ of the right Treap. It must satisfy that all node values in $\textit{u}$ are less than or equal to all node values in $\textit{v}$ . In general, the two Treaps we merge were split from one original Treap, so it is easy to ensure that all node values in $\textit{u}$ are less than those in $\textit{v}$ .

In a rotational Treap, rotations maintain the heap property of $\textit{priority}$ while preserving the tree property. In a non-rotational Treap, merging has the same effect.

Since the two Treaps are already ordered, when merging we only need to decide which tree goes “above” and which goes “below”, that is, which one becomes the subtree. Clearly, by the heap property, the one with the smaller $\textit{priority}$ goes above (we use a min-heap here).

We must also satisfy the search tree property. If the root of $\textit{u}$ has smaller $\textit{priority}$ than the root of $\textit{v}$ , then $\textit{u}$ is the new root, and because $\textit{v}$ has larger values than $\textit{u}$ , it is merged with $\textit{u}$ 's right subtree. Otherwise, $\textit{v}$ is the new root, and because the values of $u$ are smaller than those of $\textit{v}$ , it is merged with $v$ 's left subtree.

Node *merge(Node *u, Node *v) {
  // the two input trees already satisfy the search tree property internally
  // every node in u has a value < every node in v
  // therefore, the heap property must be maintained during merging
  // a min-heap is used here
  if (u == nullptr && v == nullptr) return nullptr;
  if (u != nullptr && v == nullptr) return u;
  if (v != nullptr && u == nullptr) return v;

  if (u->prio < v->prio) {
    // u has the smaller prio, so u should be the parent
    u->ch[1] = merge(u->ch[1], v);
    // since v is larger than u, make v the right subtree of u
    u->upd_siz();
    return u;
  } else {
    // v is smaller, so v should be the parent
    v->ch[0] = merge(u, v->ch[0]);
    // since u is smaller than v, use these arguments in the recursive call
    v->upd_siz();
    return v;
  }
}

Insertion

In a non-rotational Treap, basic operations such as insertion, deletion, and querying the rank by value can be implemented either with ordinary binary search tree methods or with split and merge. Generally, implementing them with split and merge is more concise, but slightly slower². To make the non-rotational Treap easier to understand, all operations below use split and merge.

When implementing insertion, we use a property of splitting: nodes whose values are at most $\textit{val}$ are placed in the first Treap.

Suppose, then, that we split the current Treap by $\textit{val}$ . We obtain the following two trees, satisfying:

\begin{aligned} T_1 &\le val\\ T_2 &> val \end{aligned}

Here $T_1$ denotes the set of nodes placed in the first split Treap, and $T_2$ denotes the second.

If we continue by splitting according to $\textit{val} - 1$ within $T_1$ , we obtain two more trees satisfying:

\begin{gathered} T_{1\ \text{left}} \le val - 1\\ T_{1\ \text{right}} > val - 1 \ \And \ T_{1\ \text{right}} \le val \end{gathered}

Here $T_{1\ \text{left}}$ denotes the set of nodes placed in the first Treap after splitting $T_1$ , and $T_{1\ \text{right}}$ denotes the second. In the expression above, the latter part $\And \ T_{1\ \text{right}} \le val$ follows from the condition satisfied by $T_1$ , namely $T_1 \le val$ .

It is easy to see that as long as $\textit{val}$ and the node values are integers (as they are in most use cases), the only node satisfying the condition for $T_{1\ \text{right}}$ is the node whose value equals $\textit{val}$ .

During insertion, if we find that a node satisfying $T_{1\ \text{right}}$ exists, we can directly increase its duplicate count; otherwise, we create a new node.

Note that after splitting the tree, we still need to use merge to “glue” it back together so that it can continue to be used. Also note that the order of the merge arguments matters: all nodes in the first tree must have values smaller than those in the second.

void insert(int val) {
  auto temp = split(root, val);
  // split the entire tree into two according to val
  // note the split implementation: the subtree equal to val is in the left subtree
  auto l_tr = split(temp.first, val - 1);
  // l_tr's left subtree <= val - 1; if a node equal to val exists, it is in the right subtree
  Node *new_node;
  if (l_tr.second == nullptr) {
    // if this node does not exist, create it; otherwise, increase its duplicate count.
    new_node = new Node(val);
  } else {
    l_tr.second->cnt++;
    l_tr.second->upd_siz();
  }
  Node *l_tr_combined =
      merge(l_tr.first, l_tr.second == nullptr ? new_node : l_tr.second);
  // merge T_1 left and T_1 right
  root = merge(l_tr_combined, temp.second);
  // merge T_1 and T_2
}

Deletion

Deletion uses a method similar to insertion: find the node whose value equals $\textit{val}$ and delete it.

void del(int val) {
  auto temp = split(root, val);
  auto l_tr = split(temp.first, val - 1);
  if (l_tr.second->cnt > 1) {
    // if this node has more than one duplicate, just decrease the count
    l_tr.second->cnt--;
    l_tr.second->upd_siz();
    l_tr.first = merge(l_tr.first, l_tr.second);
  } else {
    if (temp.first == l_tr.second) {
      // the whole T_1 may consist of only this node, so set it to null to mark deletion
      temp.first = nullptr;
    }
    delete l_tr.second;
    l_tr.second = nullptr;
  }
  root = merge(l_tr.first, temp.second);
}

Querying the rank by value

The rank is the number of nodes smaller than this value $+ 1$ . Therefore, if we split the current tree by $\textit{val} - 1$ , the first resulting tree satisfies:

T_1 \le val - 1

If the tree values and $\textit{val}$ are integers, $T_1$ contains all nodes whose values are smaller than $\textit{val}$ .

int qrank_by_val(Node* cur, int val) {
  auto temp = split(cur, val - 1);
  int ret = (temp.first == nullptr ? 0 : temp.first->siz) + 1;  // + 1 by definition
  root = merge(temp.first, temp.second);  // glue it back after splitting
  return ret;
}

Querying the value by rank

After calling split_by_rk(), three split Treaps are returned. The second contains only one node, whose rank equals $\textit{rk}$ , so we directly return this node's $\textit{val}$ .

int qval_by_rank(Node *cur, int rk) {
  Node *l, *mid, *r;
  tie(l, mid, r) = split_by_rk(cur, rk);
  int ret = mid->val;
  root = merge(merge(l, mid), r);
  return ret;
}

Querying the first node smaller than val

This problem can be transformed into finding the node with the largest rank among all nodes smaller than $\textit{val}$ . We split this Treap by $\textit{val}$ ; all nodes in the first returned Treap have values smaller than $\textit{val}$ , and then we call qval_by_rank() to find the node with the largest value in this tree.

int qprev(int val) {
  auto temp = split(root, val - 1);
  // temp.first is the subtree with values smaller than val
  int ret = qval_by_rank(temp.first, temp.first->siz);
  // query the largest value among all nodes smaller than val
  root = merge(temp.first, temp.second);
  return ret;
}

Querying the first node larger than val

Similarly, this problem can be transformed into finding the node with the smallest rank among all nodes larger than $\textit{val}$ . After splitting by $\textit{val}$ , all nodes in the second returned Treap have values greater than $\textit{val}$ .

We then query the value of the node with rank $1$ in this tree (the node with the smallest value), successfully finding the first node larger than $\textit{val}$ .

int qnex(int val) {
  auto temp = split(root, val);
  int ret = qval_by_rank(temp.second, 1);
  // query the smallest value in the subtree of all values greater than val
  root = merge(temp.first, temp.second);
  return ret;
}

Building the tree

Convert a sequence with $n$ nodes, $\{a_n\}$ , into a Treap.

We can insert the $n$ nodes by brute force. Each time we insert a node with value $v$ , split the entire Treap into the part with values at most $v$ and the part with values greater than $v$ , create a new node with value $v$ , and merge the two parts and the new node in increasing order. Each insertion takes $O(\log n)$ time, so the total time complexity is $O(n\log n)$ .

In some problems, we may need to build a tree by inserting an ordered sequence multiple times; then the tree must be built in $O(n)$ time.

Method 1: during recursive tree construction, choose the midpoint of the current interval as the root of that interval, and assign suitable priorities to every node so that the new tree satisfies the heap property. This guarantees a tree height of $O(\log n)$ .

Method 2: during recursive tree construction, choose the midpoint of the current interval as the root, and then assign each node a random priority. This guarantees a tree height of $O(\log n)$ but does not guarantee the heap property. This is still correct, because in a non-rotational Treap, priorities are used to make merge somewhat more random, not to guarantee the tree height.

Method 3: observe that a Treap is a Cartesian tree and use the $O(n)$ Cartesian-tree construction method, maintaining the right spine with a monotone stack.

Interval operations in a non-rotational Treap

Building the tree

A major advantage of a non-rotational Treap over a rotational Treap is that it can implement various interval operations. We use the template problem for the Artistic Balanced Tree as an example to introduce interval operations in a Treap.

You need to write a data structure (you may refer to the problem title) to maintain an ordered sequence.

It must support the following operation: reverse an interval. For example, if the original ordered sequence is $5\ 4\ 3\ 2\ 1$ and the interval to reverse is $[2,4]$ , the result is $5\ 2\ 3\ 4\ 1$ . For $100\%$ of the data, $1 \le n$ (initial interval length) $m$ (number of reversals) $\le 10^5$

In this problem, we need to reverse an interval, so we first need to consider how to build the tree; the tree we build must represent the initial interval.

We only need to insert the indices of the interval into the Treap in order. Then, an inorder traversal (left subtree first, current node second, right subtree last) produces this interval.³

We know that inserting nodes in increasing order into a naive binary search tree produces a long chain, whose inorder traversal naturally yields this interval.

As shown above, inserting nodes $1\ 2\ 3\ 4\ 5$ into a naive search tree in order also yields $1\ 2\ 3\ 4\ 5$ during inorder traversal.

However, in a Treap, after inserting nodes in increasing order, the merge operation also adjusts the tree structure according to $\textit{priority}$ . How can we ensure that the inorder traversal still always produces the correct output?

The monotone-stack construction method for Cartesian trees can help explain this problem.

Let the newly inserted node be $\textit{u}$ .

First, because nodes are inserted in increasing order, every newly inserted node is connected to the right spine of the Treap (the chain formed by starting at the root and repeatedly moving to the right subtree).

Starting at the root, the nodes on the right spine have increasing $\textit{priority}$ values (for a min-heap). We can find the first node on the right spine whose $\textit{priority}$ is greater than $\textit{u}$ ; call this node $\textit{v}$ , and replace this node with $\textit{u}$ .

Since $\textit{u}$ is certainly greater than every other node in the tree, we need to make $\textit{v}$ and its subtree the left subtree of $\textit{u}$ . At this point, $\textit{u}$ has no right subtree.

It can be seen that during inorder traversal, $\textit{u}$ is always visited last (because $\textit{u}$ is the last node on the right spine, and in an inorder traversal the right subtree is visited last).

The following figure shows the changes when inserting the nodes numbered $1 \sim 5$ in increasing order, specifically when node $5$ is inserted. It can help explain the process of insertion in increasing order.

Inserting a node

Interval reversal

The basic idea when reversing the interval $[l, r]$ is to split the tree into the three intervals $[1, l - 1],\ [l, r],\ [r + 1, n]$ , and then reverse the middle interval $[l, r]$ .³

The concrete reversal operation is to swap the positions of the left and right child of every subtree within the interval. The following figure shows the Treap after reversing the $[3, 4]$ and $[3, 5]$ intervals in the Treap above.

Interval reversal

If we reverse the interval $[l, r]$ this way, $r - l$ nodes are exchanged each time. Such frequent operations clearly cannot handle a data range of $10^5$ . Its single-reversal complexity of $O(n \times \log_2 n)$ is even worse than brute force (because, besides spending linear time exchanging nodes, we also spend $O(\log_2 n)$ time in the tree to find the nodes to exchange).

Looking again at the requirements, we can see that because only the final interval after all operations needs to be output, we do not need to perform the exchanges for real each time. Thus, we can use the lazy tag commonly used in segment trees to optimize the complexity. When exchanging, we only need to place a tag on the parent node indicating that every left and right child under this subtree needs to be swapped.

In a segment tree, we generally propagate lazy tags downward during updates and queries. This is because the range we want to update/query may not coincide with the range represented by a lazy tag, so we must first propagate the tag to ensure that the values read and updated are correct.

The same is true in a non-rotational Treap. Specifically, we split the Treap into the three trees described above, mark the middle tree with a lazy tag, and then merge the three trees. Because the interval we want to reverse may not coincide with the interval represented by the lazy tag, we need to propagate tags during splitting. Moreover, splitting and merging change the nodes represented by each node and its lazy tag, so we also need to propagate lazy tags before merging.

In other words, when the tree structure changes, and before a split or merge operation changes the left and right child information of a node, the tag should be propagated rather than afterward. A lazy tag needs to be passed to child nodes; if the left and right child information is changed before the tag is propagated, the tag loses the objects to which it should be propagated.⁴

The following is a code explanation based on ³.

Since most interval operations are the same as those of an ordinary non-rotational Treap, we explain only the parts that differ from an ordinary non-rotational Treap.

Propagating tags

Note that this lazy tag means that the positions of every child in this tree need to be swapped. Therefore, if a child of the current node also has a lazy tag, the two reversals cancel each other. If the child does not need to be reversed, this lazy tag must continue to be propagated to the child.

// this pushdown is a member function of the Node class; to_rev is the lazy tag
void pushdown() {
  swap(ch[0], ch[1]);
  if (ch[0] != nullptr) ch[0]->to_rev ^= 1;
  if (ch[1] != nullptr) ch[1]->to_rev ^= 1;
  to_rev = false;
}

void check_tag() {
  if (to_rev) pushdown();
}

Split

Note that in this problem, because of interval reversal, the $\textit{val}$ values in the Treap no longer satisfy the binary search tree property (see the figure in the interval reversal section). Therefore, we cannot decide whether to recurse into the left or right subtree based on $\textit{val}$ .

Thus, this split is more similar to splitting by rank in an ordinary non-rotational Treap: it decides whether to recurse into the left or right subtree based on the size of the current tree. In other words, we determine this based on the position of the node in the tree at the beginning.

All nodes in the first returned Treap have rank at most $\textit{sz}$ , while all nodes in the second returned Treap have rank greater than $\textit{sz}$ .

#define siz(_) (_ == nullptr ? 0 : _->siz)

pair<Node*, Node*> split(Node* cur, int sz) {
  // determine by the size of the tree
  if (cur == nullptr) return {nullptr, nullptr};
  cur->check_tag();
  // propagate before splitting
  if (sz <= siz(cur->ch[0])) {
    auto temp = split(cur->ch[0], sz);
    cur->ch[0] = temp.second;
    cur->upd_siz();
    return {temp.first, cur};
  } else {
    auto temp =
        split(cur->ch[1],
              sz - siz(cur->ch[0]) -
                  1);  // this conversion is explained in the rotational Treap section “Querying the value by rank”
    cur->ch[1] = temp.first;
    cur->upd_siz();
    return {cur, temp.second};
  }
}

Merge

The only thing to note is that lazy tags must be propagated before merging.

Node *merge(Node *sm, Node *bg) {
  // small, big
  if (sm == nullptr && bg == nullptr) return nullptr;
  if (sm != nullptr && bg == nullptr) return sm;
  if (sm == nullptr && bg != nullptr) return bg;
  sm->check_tag(), bg->check_tag();
  if (sm->prio < bg->prio) {
    sm->ch[1] = merge(sm->ch[1], bg);
    sm->upd_siz();
    return sm;
  } else {
    bg->ch[0] = merge(sm, bg->ch[0]);
    bg->upd_siz();
    return bg;
  }
}

Interval reversal

As described above, split out the three intervals $[1, l - 1],\ [l, r],\ [r + 1, n]$ , mark the middle interval, and then merge them again.

void seg_rev(int l, int r) {
  // less and more here are relative to l
  auto less = split(root, l - 1);
  // all values <= l - 1 are in the left subtree of less
  auto more = split(less.second, r - l + 1);
  // the interval containing the first r - l + 1 elements starting from l
  more.first->to_rev = true;
  root = merge(less.first, merge(more.first, more.second));
}

Printing the inorder traversal

Remember to propagate tags when printing.

void print(Node* cur) {
  if (cur == nullptr) return;
  cur->check_tag();
  // inorder traversal -> left subtree, then self, then right subtree
  print(cur->ch[0]);
  cout << cur->val << " ";
  print(cur->ch[1]);
}

Complete code

Rotating treap

Pointer implementation

Complete code

The following is the complete version of the code discussed above, serving as a template for an ordinary balanced tree.

// author: (ttzytt)[ttzytt.com]
#include <cstdint>
#include <cstdio>
#include <cstdlib>
using namespace std;

struct Node {
  Node *ch[2];
  int val, rank;
  int rep_cnt;
  int siz;

  Node(int val) : val(val), rep_cnt(1), siz(1) {
    ch[0] = ch[1] = nullptr;
    rank = rand();
  }

  void upd_siz() {
    siz = rep_cnt;
    if (ch[0] != nullptr) siz += ch[0]->siz;
    if (ch[1] != nullptr) siz += ch[1]->siz;
  }
};

class Treap {
 private:
  Node *root;

  constexpr static int NIL = -1;  // used to indicate that the queried value does not exist

  enum rot_type { LF = 1, RT = 0 };

  int q_prev_tmp = 0, q_nex_tmp = 0;

  void _rotate(Node *&cur, rot_type dir) {  // 0 means a right rotation, 1 means a left rotation
    Node *tmp = cur->ch[dir];
    cur->ch[dir] = tmp->ch[!dir];
    tmp->ch[!dir] = cur;
    cur->upd_siz(), tmp->upd_siz();
    cur = tmp;
  }

  void _insert(Node *&cur, int val) {
    if (cur == nullptr) {
      cur = new Node(val);
      return;
    } else if (val == cur->val) {
      cur->rep_cnt++;
      cur->siz++;
    } else if (val < cur->val) {
      _insert(cur->ch[0], val);
      if (cur->ch[0]->rank < cur->rank) {
        _rotate(cur, RT);
      }
      cur->upd_siz();
    } else {
      _insert(cur->ch[1], val);
      if (cur->ch[1]->rank < cur->rank) {
        _rotate(cur, LF);
      }
      cur->upd_siz();
    }
  }

  void _del(Node *&cur, int val) {
    if (val > cur->val) {
      _del(cur->ch[1], val);
      cur->upd_siz();
    } else if (val < cur->val) {
      _del(cur->ch[0], val);
      cur->upd_siz();
    } else {
      if (cur->rep_cnt > 1) {
        cur->rep_cnt--, cur->siz--;
        return;
      }
      uint8_t state = 0;
      state |= (cur->ch[0] != nullptr);
      state |= ((cur->ch[1] != nullptr) << 1);
      // 00: neither child exists, 01: only the left child exists, 10: only the right child exists, 11: both children exist
      Node *tmp = cur;
      switch (state) {
        case 0:
          delete cur;
          cur = nullptr;
          break;
        case 1:  // only the left child exists
          cur = tmp->ch[0];
          delete tmp;
          break;
        case 2:  // only the right child exists
          cur = tmp->ch[1];
          delete tmp;
          break;
        case 3:
          rot_type dir = cur->ch[0]->rank < cur->ch[1]->rank ? RT : LF;
          _rotate(cur, dir);
          _del(cur->ch[!dir], val);
          cur->upd_siz();
          break;
      }
    }
  }

  int _query_rank(Node *cur, int val) {
    int less_siz = cur->ch[0] == nullptr ? 0 : cur->ch[0]->siz;
    if (val == cur->val)
      return less_siz + 1;
    else if (val < cur->val) {
      if (cur->ch[0] != nullptr)
        return _query_rank(cur->ch[0], val);
      else
        return 1;
    } else {
      if (cur->ch[1] != nullptr)
        return less_siz + cur->rep_cnt + _query_rank(cur->ch[1], val);
      else
        return cur->siz + 1;
    }
  }

  int _query_val(Node *cur, int rank) {
    int less_siz = cur->ch[0] == nullptr ? 0 : cur->ch[0]->siz;
    if (rank <= less_siz)
      return _query_val(cur->ch[0], rank);
    else if (rank <= less_siz + cur->rep_cnt)
      return cur->val;
    else
      return _query_val(cur->ch[1], rank - less_siz - cur->rep_cnt);
  }

  int _query_prev(Node *cur, int val) {
    if (val <= cur->val) {
      if (cur->ch[0] != nullptr) return _query_prev(cur->ch[0], val);
    } else {
      q_prev_tmp = cur->val;
      if (cur->ch[1] != nullptr) _query_prev(cur->ch[1], val);
      return q_prev_tmp;
    }
    return NIL;
  }

  int _query_nex(Node *cur, int val) {
    if (val >= cur->val) {
      if (cur->ch[1] != nullptr) return _query_nex(cur->ch[1], val);
    } else {
      q_nex_tmp = cur->val;
      if (cur->ch[0] != nullptr) _query_nex(cur->ch[0], val);
      return q_nex_tmp;
    }
    return NIL;
  }

 public:
  void insert(int val) { _insert(root, val); }

  void del(int val) { _del(root, val); }

  int query_rank(int val) { return _query_rank(root, val); }

  int query_val(int rank) { return _query_val(root, rank); }

  int query_prev(int val) { return _query_prev(root, val); }

  int query_nex(int val) { return _query_nex(root, val); }
};

Treap tr;

int main() {
  srand(0);
  int t;
  scanf("%d", &t);
  while (t--) {
    int mode;
    int num;
    scanf("%d%d", &mode, &num);
    switch (mode) {
      case 1:
        tr.insert(num);
        break;
      case 2:
        tr.del(num);
        break;
      case 3:
        printf("%d\n", tr.query_rank(num));
        break;
      case 4:
        printf("%d\n", tr.query_val(num));
        break;
      case 5:
        printf("%d\n", tr.query_prev(num));
        break;
      case 6:
        printf("%d\n", tr.query_nex(num));
        break;
    }
  }
}

Array implementation

The following is the BZOJ ordinary balanced tree template code, implemented using arrays.

Complete code

#include <iostream>

constexpr int MAXN = 100005;
constexpr int INF = 1 << 30;

int n;

struct treap {  // directly maintains the data structure and can be used directly
  int l[MAXN], r[MAXN], val[MAXN], rnd[MAXN], size_[MAXN], w[MAXN];
  int sz, ans, rt;

  void pushup(int x) { size_[x] = size_[l[x]] + size_[r[x]] + w[x]; }

  void lrotate(int &k) {
    int t = r[k];
    r[k] = l[t];
    l[t] = k;
    size_[t] = size_[k];
    pushup(k);
    k = t;
  }

  void rrotate(int &k) {
    int t = l[k];
    l[k] = r[t];
    r[t] = k;
    size_[t] = size_[k];
    pushup(k);
    k = t;
  }

  void insert(int &k, int x) {  // insert
    if (!k) {
      sz++;
      k = sz;
      size_[k] = 1;
      w[k] = 1;
      val[k] = x;
      rnd[k] = rand();
      return;
    }
    size_[k]++;
    if (val[k] == x) {
      w[k]++;
    } else if (val[k] < x) {
      insert(r[k], x);
      if (rnd[r[k]] < rnd[k]) lrotate(k);
    } else {
      insert(l[k], x);
      if (rnd[l[k]] < rnd[k]) rrotate(k);
    }
  }

  bool del(int &k, int x) {  // delete node
    if (!k) return false;
    if (val[k] == x) {
      if (w[k] > 1) {
        w[k]--;
        size_[k]--;
        return true;
      }
      if (l[k] == 0 || r[k] == 0) {
        k = l[k] + r[k];
        return true;
      } else if (rnd[l[k]] < rnd[r[k]]) {
        rrotate(k);
        return del(k, x);
      } else {
        lrotate(k);
        return del(k, x);
      }
    } else if (val[k] < x) {
      bool succ = del(r[k], x);
      if (succ) size_[k]--;
      return succ;
    } else {
      bool succ = del(l[k], x);
      if (succ) size_[k]--;
      return succ;
    }
  }

  int queryrank(int k, int x) {
    if (!k) return 0;
    if (val[k] == x)
      return size_[l[k]] + 1;
    else if (x > val[k]) {
      return size_[l[k]] + w[k] + queryrank(r[k], x);
    } else
      return queryrank(l[k], x);
  }

  int querynum(int k, int x) {
    if (!k) return 0;
    if (x <= size_[l[k]])
      return querynum(l[k], x);
    else if (x > size_[l[k]] + w[k])
      return querynum(r[k], x - size_[l[k]] - w[k]);
    else
      return val[k];
  }

  void querypre(int k, int x) {
    if (!k) return;
    if (val[k] < x)
      ans = k, querypre(r[k], x);
    else
      querypre(l[k], x);
  }

  void querysub(int k, int x) {
    if (!k) return;
    if (val[k] > x)
      ans = k, querysub(l[k], x);
    else
      querysub(r[k], x);
  }
} T;

using std::cin;
using std::cout;

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  srand(123);
  cin >> n;
  int opt, x;
  for (int i = 1; i <= n; i++) {
    cin >> opt >> x;
    if (opt == 1)
      T.insert(T.rt, x);
    else if (opt == 2)
      T.del(T.rt, x);
    else if (opt == 3) {
      cout << T.queryrank(T.rt, x) << '\n';
    } else if (opt == 4) {
      cout << T.querynum(T.rt, x) << '\n';
    } else if (opt == 5) {
      T.ans = 0;
      T.querypre(T.rt, x);
      cout << T.val[T.ans] << '\n';
    } else if (opt == 6) {
      T.ans = 0;
      T.querysub(T.rt, x);
      cout << T.val[T.ans] << '\n';
    }
  }
  return 0;
}

Non-rotating treap

Pointer implementation

Complete code

The following is the complete version of the code discussed above, serving as a template for an ordinary balanced tree.


// author: (ttzytt)[ttzytt.com]
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <tuple>
using namespace std;

struct Node {
  Node *ch[2];
  int val, prio;
  int cnt;
  int siz;

  Node(int _val) : val(_val), cnt(1), siz(1) {
    ch[0] = ch[1] = nullptr;
    prio = rand();
  }

  Node(Node *_node) {
    val = _node->val, prio = _node->prio, cnt = _node->cnt, siz = _node->siz;
  }

  void upd_siz() {
    siz = cnt;
    if (ch[0] != nullptr) siz += ch[0]->siz;
    if (ch[1] != nullptr) siz += ch[1]->siz;
  }
};

struct none_rot_treap {
#define _3 second.second
#define _2 second.first
  Node *root;

  pair<Node *, Node *> split(Node *cur, int key) {
    if (cur == nullptr) return {nullptr, nullptr};
    if (cur->val <= key) {
      auto temp = split(cur->ch[1], key);
      cur->ch[1] = temp.first;
      cur->upd_siz();
      return {cur, temp.second};
    } else {
      auto temp = split(cur->ch[0], key);
      cur->ch[0] = temp.second;
      cur->upd_siz();
      return {temp.first, cur};
    }
  }

  tuple<Node *, Node *, Node *> split_by_rk(Node *cur, int rk) {
    if (cur == nullptr) return {nullptr, nullptr, nullptr};
    int ls_siz = cur->ch[0] == nullptr ? 0 : cur->ch[0]->siz;
    if (rk <= ls_siz) {
      Node *l, *mid, *r;
      tie(l, mid, r) = split_by_rk(cur->ch[0], rk);
      cur->ch[0] = r;
      cur->upd_siz();
      return {l, mid, cur};
    } else if (rk <= ls_siz + cur->cnt) {
      Node *lt = cur->ch[0];
      Node *rt = cur->ch[1];
      cur->ch[0] = cur->ch[1] = nullptr;
      return {lt, cur, rt};
    } else {
      Node *l, *mid, *r;
      tie(l, mid, r) = split_by_rk(cur->ch[1], rk - ls_siz - cur->cnt);
      cur->ch[1] = l;
      cur->upd_siz();
      return {cur, mid, r};
    }
  }

  Node *merge(Node *u, Node *v) {
    if (u == nullptr && v == nullptr) return nullptr;
    if (u != nullptr && v == nullptr) return u;
    if (v != nullptr && u == nullptr) return v;
    if (u->prio < v->prio) {
      u->ch[1] = merge(u->ch[1], v);
      u->upd_siz();
      return u;
    } else {
      v->ch[0] = merge(u, v->ch[0]);
      v->upd_siz();
      return v;
    }
  }

  void insert(int val) {
    auto temp = split(root, val);
    auto l_tr = split(temp.first, val - 1);
    Node *new_node;
    if (l_tr.second == nullptr) {
      new_node = new Node(val);
    } else {
      l_tr.second->cnt++;
      l_tr.second->upd_siz();
    }
    Node *l_tr_combined =
        merge(l_tr.first, l_tr.second == nullptr ? new_node : l_tr.second);
    root = merge(l_tr_combined, temp.second);
  }

  void del(int val) {
    auto temp = split(root, val);
    auto l_tr = split(temp.first, val - 1);
    if (l_tr.second->cnt > 1) {
      l_tr.second->cnt--;
      l_tr.second->upd_siz();
      l_tr.first = merge(l_tr.first, l_tr.second);
    } else {
      if (temp.first == l_tr.second) {
        temp.first = nullptr;
      }
      delete l_tr.second;
      l_tr.second = nullptr;
    }
    root = merge(l_tr.first, temp.second);
  }

  int qrank_by_val(Node *cur, int val) {
    auto temp = split(cur, val - 1);
    int ret = (temp.first == nullptr ? 0 : temp.first->siz) + 1;
    root = merge(temp.first, temp.second);
    return ret;
  }

  int qval_by_rank(Node *cur, int rk) {
    Node *l, *mid, *r;
    tie(l, mid, r) = split_by_rk(cur, rk);
    int ret = mid->val;
    root = merge(merge(l, mid), r);
    return ret;
  }

  int qprev(int val) {
    auto temp = split(root, val - 1);
    int ret = qval_by_rank(temp.first, temp.first->siz);
    root = merge(temp.first, temp.second);
    return ret;
  }

  int qnex(int val) {
    auto temp = split(root, val);
    int ret = qval_by_rank(temp.second, 1);
    root = merge(temp.first, temp.second);
    return ret;
  }
};

none_rot_treap tr;

int main() {
  srand(time(nullptr));
  int t;
  scanf("%d", &t);
  while (t--) {
    int mode;
    int num;
    scanf("%d%d", &mode, &num);
    switch (mode) {
      case 1:
        tr.insert(num);
        break;
      case 2:
        tr.del(num);
        break;
      case 3:
        printf("%d\n", tr.qrank_by_val(tr.root, num));
        break;
      case 4:
        printf("%d\n", tr.qval_by_rank(tr.root, num));
        break;
      case 5:
        printf("%d\n", tr.qprev(num));
        break;
      case 6:
        printf("%d\n", tr.qnex(num));
        break;
    }
  }
}

Range operations with a non-rotating treap

Pointer implementation

Complete code

The following is the complete version of the code discussed above, serving as a template for the sequence-maintenance balanced tree problem.


// author: (ttzytt)[ttzytt.com]
#include <cstdlib>
#include <ctime>
#include <iostream>
using namespace std;

// reference: https://www.cnblogs.com/Equinox-Flower/p/10785292.html
struct Node {
  Node* ch[2];
  int val, prio;
  int cnt;
  int siz;
  bool to_rev = false;  // reverse every node in this subtree

  Node(int _val) : val(_val), cnt(1), siz(1) {
    ch[0] = ch[1] = nullptr;
    prio = rand();
  }

  int upd_siz() {
    siz = cnt;
    if (ch[0] != nullptr) siz += ch[0]->siz;
    if (ch[1] != nullptr) siz += ch[1]->siz;
    return siz;
  }

  void pushdown() {
    swap(ch[0], ch[1]);
    if (ch[0] != nullptr) ch[0]->to_rev ^= 1;
    // If a child was already marked for reversal, the two reversals cancel; otherwise, this
    // tag needs to be pushed down to the child
    if (ch[1] != nullptr) ch[1]->to_rev ^= 1;
    to_rev = false;
  }

  void check_tag() {
    if (to_rev) pushdown();
  }
};

struct Seg_treap {
  Node* root;
#define siz(_) (_ == nullptr ? 0 : _->siz)

  pair<Node*, Node*> split(Node* cur, int sz) {
    // partition according to the size of the tree
    if (cur == nullptr) return {nullptr, nullptr};
    cur->check_tag();
    if (sz <= siz(cur->ch[0])) {
      // the left subtree is sufficient
      auto temp = split(cur->ch[0], sz);
      // the left subtree may not be needed in its entirety; temp.second is the part that is not needed
      cur->ch[0] = temp.second;
      cur->upd_siz();
      return {temp.first, cur};
    } else {
      // the left side plus part of the right side (including this node itself, of course)
      auto temp = split(cur->ch[1], sz - siz(cur->ch[0]) - 1);
      cur->ch[1] = temp.first;
      cur->upd_siz();
      return {cur, temp.second};
    }
  }

  Node* merge(Node* sm, Node* bg) {
    // small, big
    if (sm == nullptr && bg == nullptr) return nullptr;
    if (sm != nullptr && bg == nullptr) return sm;
    if (sm == nullptr && bg != nullptr) return bg;
    sm->check_tag(), bg->check_tag();
    if (sm->prio < bg->prio) {
      sm->ch[1] = merge(sm->ch[1], bg);
      sm->upd_siz();
      return sm;
    } else {
      bg->ch[0] = merge(sm, bg->ch[0]);
      bg->upd_siz();
      return bg;
    }
  }

  void insert(int val) {
    auto temp = split(root, val);
    auto l_tr = split(temp.first, val - 1);
    Node* new_node;
    if (l_tr.second == nullptr) new_node = new Node(val);
    Node* l_tr_combined =
        merge(l_tr.first, l_tr.second == nullptr ? new_node : l_tr.second);
    root = merge(l_tr_combined, temp.second);
  }

  void seg_rev(int l, int r) {
    // Here, less and more are relative to l
    auto less = split(root, l - 1);
    // Everything less than or equal to l - 1 is on the left side of less
    auto more = split(less.second, r - l + 1);
    // take the first r - l + 1 elements starting from l
    more.first->to_rev = true;
    root = merge(less.first, merge(more.first, more.second));
  }

  void print(Node* cur) {
    if (cur == nullptr) return;
    cur->check_tag();
    print(cur->ch[0]);
    cout << cur->val << " ";
    print(cur->ch[1]);
  }
};

Seg_treap tr;

int main() {
  srand(time(nullptr));
  int n, m;
  cin >> n >> m;
  for (int i = 1; i <= n; i++) tr.insert(i);
  while (m--) {
    int l, r;
    cin >> l >> r;
    tr.seg_rev(l, r);
  }
  tr.print(tr.root);
}

Examples

Ordinary balanced tree

Sequence-maintenance balanced tree (Splay)

“ZJOI2006” Bookshelf

“NOI2005” Sequence Maintenance

CF 702F T-Shirts

References and notes

Footnotes

This illustration was designed with reference to the illustration in Wikipedia’s treap entry ↩
https://charleswu.site/archives/1051 ↩
https://www.cnblogs.com/Equinox-Flower/p/10785292.html ↩ ↩² ↩³
https://www.luogu.com.cn/blog/85514/fhq-treap-xue-xi-bi-ji ↩