Efficient implementation of the implicit treap data structure.
What does this package provide?
This package implements a tree-like data structure called implicit treap. This
data structure implements interface similar to random-access arrays, but with
fast (logarithmic time complexity)
rotate operations. In addition,
treap allows you to specify and measure values of any monoids on a segment,
like a sum of elements or minimal element on some contiguous part of the array.
When to use this package?
Use this package when you want the following operations to be fast:
- Access elements by index.
- Insert elements by index.
- Delete elements by index.
- Calculate monoidal operation (like sum, product, min, etc.) of all elements between two indices.
- Call slicing operations like
Below you can find the table of time complexity for all operations (where
the size of the treap):
||Get number of elements in the treap|
||Access by index|
||Insert by index|
||Delete by index|
||Measure monoid on the segment|
||Split treap by index into two treaps|
||Merge two treaps into a single one|
The package also comes with nice pretty-printing!
ghci> t = fromList [1..5] :: RTreap (Sum Int) Int ghci> prettyPrint t 5,15:2 ╱╲ ╱ ╲ ╱ ╲ ╱ ╲ 1,1:1 3,12:4 ╱╲ ╱ ╲ ╱ ╲ 1,3:3 1,5:5
If you don't need to calculate monoidal operations, you may alternatively use
containers package as it provides more extended interface but doesn't
allow to measure monoidal values on segments.