A dynamic, sparse 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 DynSparseSegTree of capacity $n$ for interval $[l_0, r_0)$ with mempty as initial leaf values.

Since: 1.2.1.0

$O(1)$ Returns recommended capacity for $L$ and $q$: $2q \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(\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)$ 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