A dynamic segment tree that covers a half-open interval $[l_0, r_0)$. Is is dynamic in that the nodes are instantinated as needed.

Since: 1.2.1.0

Strongly typed index of pool items. User has to explicitly corece on raw index use.

$O(n)$ Creates a DynSegTree of capacity $n$ for interval $[l_0, r_0)$ with mempty as initial leaf values.

Since: 1.2.1.0

$O(n)$ Creates a DynSegTree of capacity $n$ for interval $[l_0, r_0)$ with initial monoid value assignment $g(l, r)$.

Since: 1.2.1.0

$O(1)$ Returns recommended capacity for $L$ and $q$: about $q \log_2 L$.

Since: 1.2.1.0

$O(1)$ Creates a new root in $[l_0, r_0)$.

Since: 1.2.1.0

$O(L)$ Creates a new root node with contiguous leaf values. User would want to use a strict segment tree instead.

Constraints

• $[l_0, r_0) = [0, L)$: The index boundary of the segment tree must match the sequence.

Since: 1.2.1.0

$O(\log L)$ Writes to the monoid value of the node at $i$.

Constraints

• $l_0 \le i \lt r_0$

Since: 1.2.1.0

$O(\log L)$ Modifies the monoid value of the node at $i$.

Constraints

• $l_0 \le i \lt r_0$

Since: 1.2.1.0

$O(\log L)$ Modifies the monoid value of the node at $i$.

Constraints

• $l_0 \le i \lt r_0$

Since: 1.2.1.0

$O(\log L)$ Returns the monoid product in $[l, r)$.

Constraints

• $l_0 \le l \le r \le r_0$

Since: 1.2.1.0

$O(\log L)$ Returns the monoid product in $[l_0, r_0)$.

Since: 1.2.1.0

$O(\log L)$ Resets an interval $[l, r)$ to initial monoid values.

Constraints

• $l_0 \le l \le r \le r_0$

Since: 1.2.1.0

$O(\log L)$ Returns the maximum $r \in [l_0, r_0)$ where $f(a_{l_0} a_{l_0 + 1} \dots a_{r - 1})$ holds.

Since: 1.2.1.0

$O(\log L)$ Returns the maximum $r \in [l_0, r_0)$ where $f(a_{l_0} a_{l_0 + 1} \dots a_{r - 1})$ holds.

Since: 1.2.1.0

$O(\log L)$ Claers all the nodes from the storage.

Since: 1.2.2.0