Size of the Treap data structure. Guaranteed to be always non-negative.

Priority in the Treap data structure.

Treap data structure.

\( O(1) \). Creates empty Treap.

\( O(1) \). Creates singleton Treap.

\( O(1) \). Returns the number of the elements in the Treap. Always non-negative.

Properties:

• \( \forall (t\ ::\ \mathrm{Treap}\ m\ a)\ .\ \mathrm{size}\ t \geqslant 0 \)

Take size of the Treap as Int.

\( O(1) \). Returns accumulated value in the root of the tree.

\( O(d) \). Lookup a value inside Treap by a given index.

\( O(d) \). Return value of monoidal accumulator on a segment [l, r).

\( O(d) \). splitAt i t splits Treap by the given index into two treaps (t1, t2) such that the following properties hold:

1. \( \mathrm{size}\ t_1 = i \)
2. \( \mathrm{size}\ t_2 = n - i \)
3. \( \mathrm{merge}\ t_1\ t_2 \equiv t \)

Special cases:

1. If \( i \leqslant 0 \) then the result is (empty, t).
2. If \( i \geqslant n \) then the result is (t, empty).

\( O(\max\ d_1\ d_2) \). Merge two Treaps into single one.

>>> pone p a = one (Priority p) a :: Treap (Sum Int) Int
>>> prettyPrint $ merge (merge (pone 1 3) (pone 4 5)) (merge (pone 3 0) (pone 5 9))
   4,17:9
     ╱
   3,8:5
     ╱╲
    ╱  ╲
   ╱    ╲
1,3:3 1,0:0

\( O(d) \). take n t returns Treap that contains first n elements of the given Treap t.

Special cases:

1. If \( i \leqslant 0 \) then the result is empty.
2. If \( i \geqslant n \) then the result is t.

\( O(d) \). drop n t returns Treap without first n elements of the given Treap t.

Special cases:

1. If \( i \leqslant 0 \) then the result is t.
2. If \( i \geqslant n \) then the result is empty.

\( O(d) \). Rotate a Treap to the right by a given number of elements modulo treap size. In simple words, rotate n t takes first n elements of t and puts them at the end of t in the same order. If the given index is negative, then this function rotates left.

\( O(d) \). Insert a value into Treap with given key and priority. Updates monoidal accumulator accordingly.

\( O(d) \). Delete element from Treap by the given index. If index is out of bounds, Treap remains unchanged.

\( O(1) \). Calculate size and the value of the monoidal accumulator in the given root node. This function doesn't perform any recursive calls and it assumes that the values in the children are already correct. So use this function only in bottom-up manner.