A balanced binary search tree. More...

#include <splaytree.hpp>

Public Member Functions
	SplayTree ()
	Initialises empty splay tree.

	SplayTree (int n)
	Initialises the splay tree with `n` elements, all equal to the identity element `T::id()`.

	SplayTree (const vector< T > &v)
	Initialises the splay tree with values from vector `v`.

int	size ()
	Gets the number of elements in the splay tree.

void	set (int k, T x)
	Set the `k`-th index (0-indexed) to `x`.

T	get (int k)
	Get the value at the `k`-th index (0-indexed).

void	update (int l, int r, L x)
	Apply update `x` to the half-open interval `[l, r)`.

T	query (int l, int r)
	Query the half-open interval `[l, r)`.

template<typename P>
int	max_right (int l, P pred)
	Finds the largest `x` such that the predicate returns true for the left-associative fold on the half-open interval `[l, x)`.

template<bool(*)(T) pred>
int	max_right (int l)
	This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

template<typename P>
int	min_left (int r, P pred)
	Finds the smallest `x` such that the predicate returns true for the left-associative fold on the half-open interval `[x, r)`.

template<bool(*)(T) pred>
int	min_left (int r)
	This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

void	reverse (int l, int r)
	Reverses the half-open interval `[l, r)`.

void	insert (int k, T x)
	Inserts `x` into the `k`-th index (0-indexed).

void	erase (int k)
	Erases the value at the `k`-th index (0-indexed).

splaytree	split (int k)
	Splits `this` into two parts, then, set `this` to be the left part and returns the right part.

pair< splaytree, splaytree >	split (int l, int r)
	Splits `this` into three parts, then, set `this` to be the left part and returns the middle and right parts.

void	merge (splaytree &o)
	Merge splay tree `o` to the right of `this`.

void	merge (splaytree &b, splaytree &c)
	Merge splay tree `b` to the right of `this`, then `c` to the right of `this` and `b`.

Detailed Description

template<Monoid T, Lazy< T > L, bool store_reverse = false>
struct maomao90::SplayTree< T, L, store_reverse >

A balanced binary search tree.

Supports operations similar to a LazySegTree. Additionally, also supports splitting, merging, and range reversals. All operations work in ammortised $O(\log_2 n)$ time. Note that all indices are 0-indexed, and all intervals are half-open: [start, end).

Template Parameters

T	the monoid to be stored in the treap. Note that the `merge` function is called using `left_monoid.merge(right_monoid)`.
L	the type used to perform range updates on `T`. Note that the `merge` function is called using `new_update.merge(old_update)`.
store_reverse	should be `true` only if range reversal is required and `T` is not commutative.

Constructor & Destructor Documentation

◆ SplayTree() [1/3]

template<Monoid T, Lazy< T > L, bool store_reverse = false>

maomao90::SplayTree< T, L, store_reverse >::SplayTree ( )

inline

Initialises empty splay tree.

◆ SplayTree() [2/3]

template<Monoid T, Lazy< T > L, bool store_reverse = false>

maomao90::SplayTree< T, L, store_reverse >::SplayTree ( int n )

inlineexplicit

Initialises the splay tree with n elements, all equal to the identity element T::id().

Parameters

n	the number of elements to be initialised with.

◆ SplayTree() [3/3]

template<Monoid T, Lazy< T > L, bool store_reverse = false>

maomao90::SplayTree< T, L, store_reverse >::SplayTree ( const vector< T > & v )

inlineexplicit

Initialises the splay tree with values from vector v.

Parameters

v	the vector of values to be stored in the splay tree.

Member Function Documentation

◆ size()

template<Monoid T, Lazy< T > L, bool store_reverse = false>

int maomao90::SplayTree< T, L, store_reverse >::size ( )

inline

Gets the number of elements in the splay tree.

Returns: the number of elements in the splay tree.

◆ set()

template<Monoid T, Lazy< T > L, bool store_reverse = false>

void maomao90::SplayTree< T, L, store_reverse >::set	(	int	k,
		T	x )

inline

Set the k-th index (0-indexed) to x.

Parameters

k	the index to set.
x	the value to set.

Precondition: 0 <= k < size().

◆ get()

template<Monoid T, Lazy< T > L, bool store_reverse = false>

T maomao90::SplayTree< T, L, store_reverse >::get ( int k )

inline

Get the value at the k-th index (0-indexed).

Parameters

k	the index to get the value of.

Returns: the value at the k-th index.

Precondition: 0 <= k < size().

◆ update()

template<Monoid T, Lazy< T > L, bool store_reverse = false>

void maomao90::SplayTree< T, L, store_reverse >::update	(	int	l,
		int	r,
		L	x )

inline

Apply update x to the half-open interval [l, r).

Parameters

l	the inclusive left endpoint (0-indexed) of the interval.
r	the exclusive right endpoint (0-indexed) of the interval.
x	the update to be applied.

Precondition: 0 <= l <= r <= size().

◆ query()

template<Monoid T, Lazy< T > L, bool store_reverse = false>

T maomao90::SplayTree< T, L, store_reverse >::query	(	int	l,
		int	r )

inline

Query the half-open interval [l, r).

Parameters

l	the inclusive left endpoint (0-indexed) of the interval.
r	the exclusive right endpoint (0-indexed) of the interval.

Returns: the result of the left-associative fold in the interval.

Precondition: 0 <= l <= r <= size().

◆ max_right() [1/2]

template<Monoid T, Lazy< T > L, bool store_reverse = false>

template<typename P>

int maomao90::SplayTree< T, L, store_reverse >::max_right	(	int	l,
		P	pred )

inline

Finds the largest x such that the predicate returns true for the left-associative fold on the half-open interval [l, x).

Template Parameters

P	the type of the predicate function.

Parameters

l	the inclusive left endpoint (0-indexed) to search to the right of.
pred	a function that accepts `T` as a parameter, and returns a boolean.

Returns: the largest x such that pred(query(l, x)) is true. Note that the query function is exclusive of the right endpoint.

Precondition: 0 <= l <= size().; pred(T::id()) = true. In other words, pred should be true for query(l, l).

◆ max_right() [2/2]

template<Monoid T, Lazy< T > L, bool store_reverse = false>

template<bool(*)(T) pred>

int maomao90::SplayTree< T, L, store_reverse >::max_right ( int l )

inline

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

◆ min_left() [1/2]

template<Monoid T, Lazy< T > L, bool store_reverse = false>

template<typename P>

int maomao90::SplayTree< T, L, store_reverse >::min_left	(	int	r,
		P	pred )

inline

Finds the smallest x such that the predicate returns true for the left-associative fold on the half-open interval [x, r).

Template Parameters

P	the type of the predicate function.

Parameters

r	the exclusive right endpoint (0-indexed) to search to the left of.
pred	a function that accepts `T` as a parameter, and returns a boolean.

Returns: the smallest x such that pred(query(x, r)) is true. Note that the query function is exclusive of the right endpoint.

Precondition: 0 <= r <= size().; pred(T::id()) = true. In other words, pred should be true for query(r, r).

◆ min_left() [2/2]

template<Monoid T, Lazy< T > L, bool store_reverse = false>

template<bool(*)(T) pred>

int maomao90::SplayTree< T, L, store_reverse >::min_left ( int r )

inline

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

◆ reverse()

template<Monoid T, Lazy< T > L, bool store_reverse = false>

void maomao90::SplayTree< T, L, store_reverse >::reverse	(	int	l,
		int	r )

inline

Reverses the half-open interval [l, r).

Parameters

l	the inclusive left endpoint (0-indexed) of the interval.
r	the exclusive right endpoint (0-indexed) of the interval.

Precondition: 0 <= l <= r <= size().

◆ insert()

template<Monoid T, Lazy< T > L, bool store_reverse = false>

void maomao90::SplayTree< T, L, store_reverse >::insert	(	int	k,
		T	x )

inline

Inserts x into the k-th index (0-indexed).

For example, if k = 0, x is inserted at the start, and if k = size(), x is inserted at the end.

Parameters

k	the index to insert the value into.
x	the value to insert.

Precondition: 0 <= k <= size().

◆ erase()

template<Monoid T, Lazy< T > L, bool store_reverse = false>

void maomao90::SplayTree< T, L, store_reverse >::erase ( int k )

inline

Erases the value at the k-th index (0-indexed).

Parameters

k	the index to erase.

Precondition: 0 <= k < size().

◆ split() [1/2]

template<Monoid T, Lazy< T > L, bool store_reverse = false>

splaytree maomao90::SplayTree< T, L, store_reverse >::split ( int k )

inline

Splits this into two parts, then, set this to be the left part and returns the right part.

Parameters

k	the number of elements in the left part after the split.

Returns: the splay tree containing the remaining size() - k elements.

◆ split() [2/2]

template<Monoid T, Lazy< T > L, bool store_reverse = false>

pair< splaytree, splaytree > maomao90::SplayTree< T, L, store_reverse >::split	(	int	l,
		int	r )

inline

Splits this into three parts, then, set this to be the left part and returns the middle and right parts.

Parameters

l	the number of elements in the left part after the split.
r	the total number of elements in the left and middle part, i.e., the middle part has `r - l` elements.

Returns: a pair (middle, right) where middle is the middle splay tree containing r - l elements and right is the right splay tree containing size() - r elements.

Precondition: 0 <= l <= r <= size().

◆ merge() [1/2]

template<Monoid T, Lazy< T > L, bool store_reverse = false>

void maomao90::SplayTree< T, L, store_reverse >::merge ( splaytree & o )

inline

Merge splay tree o to the right of this.

Parameters

o	the splay tree to merge to the right of `this`.

Postcondition: o points to an empty splay tree.

◆ merge() [2/2]

template<Monoid T, Lazy< T > L, bool store_reverse = false>

void maomao90::SplayTree< T, L, store_reverse >::merge	(	splaytree &	b,
		splaytree &	c )

inline

Merge splay tree b to the right of this, then c to the right of this and b.

Parameters

b	the middle splay tree after merging.
c	the right splay tree after merging.

Postcondition: b and c points to empty splay trees.

The documentation for this struct was generated from the following file:

library/data_structure/splaytree.hpp

Public Member Functions

Detailed Description

Constructor & Destructor Documentation

◆ SplayTree() [1/3]

◆ SplayTree() [2/3]

◆ SplayTree() [3/3]

Member Function Documentation

◆ size()

◆ set()

◆ get()

◆ update()

◆ query()

◆ max_right() [1/2]

◆ max_right() [2/2]

◆ min_left() [1/2]

◆ min_left() [2/2]

◆ reverse()

◆ insert()

◆ erase()

◆ split() [1/2]

◆ split() [2/2]

◆ merge() [1/2]

◆ merge() [2/2]