Storages of dynamic sequences of monoid values with monoid actions on them through the SegAct instance.

Since: 1.2.0.0

\(O(n)\) Creates a new Seq of length \(n\).

Since: 1.2.0.0

\(O(1)\) Clears the sequence storage.

Since: 1.2.0.0

\(O(1)\) Allocates a new sequence of length \(1\).

Since: 1.2.0.0

\(O(n)\) Allocates a new sequence.

Since: 1.2.0.0

\(O(1)\) Frees a node.

Since: 1.2.0.0

\(O(n)\) Frees a subtree.

Since: 1.2.0.0

Amortized \(O(\log n)\). Merges two sequences \(l, r\) into one in the given order, ignoring empty sequences.

Constraints

• The vertices must be either null or a root.

Since: 1.2.0.0

Amortized \(O(\log n)\). Merges three sequences \(l, m, r\) into one in the given order, ignoring empty sequences.

Constraints

• The vertices must be either null or a root.

Since: 1.2.0.0

Amortized \(O(\log n)\). Merges four sequences \(l, b, c, d, m, r\) into one in the given order, ignoring empty sequences.

Constraints

• The vertices must be either null or a root.

Since: 1.2.0.0

Amortized \(O(\log n)\). Splits a sequences into two: \([0, k), [k, n)\).

Constraints

• The node must be null or a root.
• \(0 \le k \le n\).

Since: 1.2.0.0

Amortized \(O(\log n)\). Splits a sequences into three: \([0, l), [l, r), [r, n)\).

Constraints

• The node must be null or a root.
• \(0 \le l \le r \le n\).

Since: 1.2.0.0

Amortized \(O(\log n)\). Splits a sequences into four: \([0, i), [i, j), [j, k), [k, n)\).

Constraints

• The node must be null or a root.
• \(0 \le i \le j \le k \le n\).

Since: 1.2.0.0

Amortized \(O(\log n)\). Splits a sequence into three: \([0, \mathrm{root}), \mathrm{root}, [\mathrm{root} + 1, n)\).

Constraints

• The node must be a root.

Since: 1.2.0.0

Amortized \(O(\log n)\). Captures the root of a subtree of \([l, r)\). Splay the new root after call.

Constraints

• \(0 \le \lt r \le n\). Note that the interval must have positive length.

Since: 1.2.0.0

Amortized \(O(\log n)\). Reads the \(k\)-th node's monoid value.

Constraints

• \(0 \le k \lt n\)

Since: 1.2.0.0

Amortized \(O(\log n)\). Reads the \(k\)-th node's monoid value.

Constraints

• The root must be empty or a root.

Since: 1.2.0.0

Amortized \(O(\log n)\). Writes to the \(k\)-th node's monoid value.

Constraints

• The node must be a root.
• \(0 \le k \lt n\)

Since: 1.2.0.0

Amortized \(O(\log n)\). Modifies the \(k\)-th node's monoid value.

Constraints

• The node must be a root.
• \(0 \le k \lt n\)

Since: 1.2.0.0

Amortized \(O(\log n)\). Exchanges the \(k\)-th node's monoid value.

Constraints

• The node must be a root.
• \(0 \le k \lt n\)

Since: 1.2.0.0

Amortized \(O(\log n)\). Returns the monoid product in an interval \([l, r)\).

Constraints

• The node must be a root
• \(0 \le l \le r \le n\)

Since: 1.2.0.0

Amortized \(O(\log n)\). Returns the monoid product in an interval \([l, r)\). Returns Nothing if an invalid interval is given or for an empty sequence.

Since: 1.2.0.0

Amortized \(O(\log n)\). Returns the monoid product of the whole sequence. Returns mempty for an empty sequence.

Constraint

• The node must be null or a root.

Since: 1.2.0.0

Amortized \(O(\log n)\). Given an interval \([l, r)\), applies a monoid action \(f\).

Constraints

• \(0 \le l \le r \le n\)
• The root must point to a non-empty sequence.

Since: 1.2.0.0

\(O(1)\) Applies a monoid action \(f\) to the root of a sequence.

Since: 1.2.0.0

Amortized \(O(\log n)\). Reverses the sequence in \([l, r)\).

Constraints

• The monoid action \(f\) must be commutative.
• The monoid value \(v\) must be commutative.

Since: 1.2.0.0

Amortized \(O(\log n)\). Inserts a new node at \(k\) with initial monoid value \(v\). This functions for an empty index.

Constraints

• The node must be null or a root.
• \(0 \le k \le n\)

Since: 1.2.0.0

Amortized \(O(\log n)\). Frees the \(k\)-th node and returns the monoid value of it.

Constraints

• The node must be null or a root.
• \(0 \le k \lt n\)

Since: 1.2.0.0

Amortized \(O(\log n)\). Frees the \(k\)-th node.

Constraints

• The node must be null or a root.
• \(0 \le k \lt n\)

Since: 1.2.0.0

Amortized \(O(\log n)\). Detaches the \(k\)-th node and returns the new root of the original sequence.

Constraints

• The node must be null or a root.
• \(0 \le k \lt n\)

Since: 1.2.0.0

Amortized \(O(\log n)\). Rotates a child node.

Constraints

• \(0 \le i \lt n\)

Since: 1.2.0.0

Amortized \(O(\log n)\). Moves up a node to be a root.

Since: 1.2.0.0

Amortized \(O(\log n)\). Finds \(k\)-th node and splays it. Returns the new root.

Constraints

• \(0 \le k \lt n\)

Since: 1.2.0.0

Amortized \(O(\log n)\).

Constraints

• The node must be a root.

Since: 1.2.0.0

Amortized \(O(\log n)\).

Constraints

• The node must be a root.

Since: 1.2.0.0

Amortized \(O(\log n)\).

Constraints

• The node must be a root.

Since: 1.2.0.0

Amortized \(O(\log n)\).

Constraints

• The node must be a root.

Since: 1.2.0.0

Amortized \(O(\log n)\). Given a monotonious sequence, returns the rightmost node \(v_k\) where \(f(v)\) holds for every \([0, i) (0 \le i \lt k)\).

Constraints

• The node must be a root.

Since: 1.2.0.0

Amortized \(O(\log n)\). Given a monotonious sequence, returns the rightmost node \(v_k\) where \(f(v)\) holds for every \([0, i) (0 \le i \lt k)\).

Constraints

• The node must be a root.

Since: 1.2.0.0

Amortized \(O(\log n)\). Given a monotonious sequence, returns the rightmost node \(v_k\) where \(f(v)\) holds for every \([0, i) (0 \le i \lt k)\).

Constraints

• The node must be a root.

Since: 1.2.0.0

Amortized \(O(\log n)\). Given a monotonious sequence, returns the rightmost node \(v_k\) where \(f(v)\) holds for every \([0, i) (0 \le i \lt k)\).

Constraints

• The node must be a root.

Since: 1.2.0.0

Amortized \(O(\log n)\). Given a monotonious sequence, returns the rightmost node \(v\) where \(f(v)\) holds for every \(v_i (0 \le i \lt k)\). Note that \(f\) works for a single node, not a monoid product.

Constraints

• The node must be a root.

Since: 1.2.0.0

Amortized \(O(\log n)\). Given a monotonious sequence, returns the rightmost node \(v_k\) where \(f(v)\) holds for every \(v_i (0 \le i \le k)\). Note that \(f\) works for a single node, not a monoid product.

Constraints

• The node must be a root.

Since: 1.2.0.0

Amortized \(O(\log n)\). Given a monotonious sequence, returns the rightmost node \(v_k\) where \(f(v)\) holds for every \([0, i) (0 \le i \lt k)\).

Constraints

• The node must be a root.

Since: 1.2.0.0

Amortized \(O(\log n)\). Given a monotonious sequence, returns the rightmost node \(v_k\) where \(f(v)\) holds for every \([0, i) (0 \le i \lt k)\).

Constraints

• The node must be a root.

Since: 1.2.0.0

Amortized \(O(n)\). Returns the sequence of monoid values.

Since: 1.2.0.0