| Safe Haskell | Safe-Inferred |
|---|---|
| Language | GHC2021 |
AtCoder.Extra.DynSegTree
Description
A dynamic segment tree that covers a half-open interval \([l_0, r_0)\). Nodes are instantinated as needed, with the required capacity being approximately \(2q \log_2 L\), where \(q\) is the number of mutable operations and \(L\) is the length of the interval.
Example
>>>import AtCoder.Extra.DynSegTree qualified as Seg>>>import Data.Semigroup (Sum (..))>>>import Data.Vector.Unboxed qualified as VU
Create a DynSegTree over \([0, 4)\) with some initial capacity:
>>>let capacityFor len q = q * max 2 (2 + ceiling (logBase 2 (fromIntegral len) :: Double))>>>let len = 4; q = 2>>>seg <- Seg.new @_ @(Sum Int) (capacityFor len q) 0 4
Different from the SegTree module, it requires explicit root handle:
>>>-- [0, 0, 0, 0]>>>root <- Seg.newRoot seg>>>Seg.write seg root 1 $ Sum 10>>>Seg.write seg root 2 $ Sum 20>>>-- [0, 10, 20, 0]>>>Seg.prod seg root 0 3Sum {getSum = 30}
>>>Seg.maxRight seg root (< (Sum 30))2
Since: 1.2.1.0
Synopsis
- data DynSegTree s a = DynSegTree {}
- newtype Index = Index {}
- new :: (HasCallStack, PrimMonad m, Monoid a, Unbox a) => Int -> Int -> Int -> m (DynSegTree (PrimState m) a)
- buildWith :: (HasCallStack, PrimMonad m, Monoid a, Unbox a) => Int -> Int -> Int -> (Int -> Int -> a) -> m (DynSegTree (PrimState m) a)
- recommendedCapacity :: Int -> Int -> Int
- newRoot :: (HasCallStack, PrimMonad m, Monoid a, Unbox a) => DynSegTree (PrimState m) a -> m Index
- newSeq :: (HasCallStack, PrimMonad m, Monoid a, Unbox a) => DynSegTree (PrimState m) a -> Vector a -> m Index
- write :: (HasCallStack, PrimMonad m, Monoid a, Unbox a) => DynSegTree (PrimState m) a -> Index -> Int -> a -> m ()
- modify :: (HasCallStack, PrimMonad m, Monoid a, Unbox a) => DynSegTree (PrimState m) a -> Index -> (a -> a) -> Int -> m ()
- modifyM :: (HasCallStack, PrimMonad m, Monoid a, Unbox a) => DynSegTree (PrimState m) a -> Index -> (a -> m a) -> Int -> m ()
- prod :: (HasCallStack, PrimMonad m, Monoid a, Unbox a) => DynSegTree (PrimState m) a -> Index -> Int -> Int -> m a
- allProd :: (HasCallStack, PrimMonad m, Monoid a, Unbox a) => DynSegTree (PrimState m) a -> Index -> m a
- resetInterval :: (HasCallStack, PrimMonad m, Monoid a, Unbox a) => DynSegTree (PrimState m) a -> Index -> Int -> Int -> m ()
- maxRight :: (HasCallStack, PrimMonad m, Monoid a, Unbox a) => DynSegTree (PrimState m) a -> Index -> (a -> Bool) -> m Int
- maxRightM :: (HasCallStack, PrimMonad m, Monoid a, Unbox a) => DynSegTree (PrimState m) a -> Index -> (a -> m Bool) -> m Int
- clear :: PrimMonad m => DynSegTree (PrimState m) a -> m ()
Dynamic segment tree
data DynSegTree s a Source #
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
Constructors
| DynSegTree | |
Fields
| |
Re-exports
Strongly typed index of pool items. User has to explicitly corece on raw index use.
Instances
Constructors
Arguments
| :: (HasCallStack, PrimMonad m, Monoid a, Unbox a) | |
| => Int | Capacity \(n\) |
| -> Int | Left index boundary \(l_0\) |
| -> Int | Right index boundary \(r_0\) |
| -> m (DynSegTree (PrimState m) a) | Dynamic propagated segment tree |
\(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
Arguments
| :: (HasCallStack, PrimMonad m, Monoid a, Unbox a) | |
| => Int | Capacity \(n\) |
| -> Int | Left index boundary \(l_0)\) |
| -> Int | Right index boundary \(r_0)\) |
| -> (Int -> Int -> a) | Initial monoid value assignment \(g: (l, r) \rightarrow a\) |
| -> m (DynSegTree (PrimState m) a) | Dynamic segment tree |
\(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
recommendedCapacity :: Int -> Int -> Int Source #
\(O(1)\) Returns recommended capacity for \(L\) and \(q\): about \(q \log_2 L\).
Since: 1.2.1.0
newRoot :: (HasCallStack, PrimMonad m, Monoid a, Unbox a) => DynSegTree (PrimState m) a -> m Index Source #
\(O(1)\) Creates a new root in \([l_0, r_0)\).
Since: 1.2.1.0
newSeq :: (HasCallStack, PrimMonad m, Monoid a, Unbox a) => DynSegTree (PrimState m) a -> Vector a -> m Index Source #
\(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
Accessing elements
write :: (HasCallStack, PrimMonad m, Monoid a, Unbox a) => DynSegTree (PrimState m) a -> Index -> Int -> a -> m () Source #
\(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
modify :: (HasCallStack, PrimMonad m, Monoid a, Unbox a) => DynSegTree (PrimState m) a -> Index -> (a -> a) -> Int -> m () Source #
\(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
modifyM :: (HasCallStack, PrimMonad m, Monoid a, Unbox a) => DynSegTree (PrimState m) a -> Index -> (a -> m a) -> Int -> m () Source #
\(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
Products
prod :: (HasCallStack, PrimMonad m, Monoid a, Unbox a) => DynSegTree (PrimState m) a -> Index -> Int -> Int -> m a Source #
\(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
allProd :: (HasCallStack, PrimMonad m, Monoid a, Unbox a) => DynSegTree (PrimState m) a -> Index -> m a Source #
\(O(\log L)\) Returns the monoid product in \([l_0, r_0)\).
Since: 1.2.1.0
Tree operations
resetInterval :: (HasCallStack, PrimMonad m, Monoid a, Unbox a) => DynSegTree (PrimState m) a -> Index -> Int -> Int -> m () Source #
\(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
Binary searches
maxRight :: (HasCallStack, PrimMonad m, Monoid a, Unbox a) => DynSegTree (PrimState m) a -> Index -> (a -> Bool) -> m Int Source #
\(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
maxRightM :: (HasCallStack, PrimMonad m, Monoid a, Unbox a) => DynSegTree (PrimState m) a -> Index -> (a -> m Bool) -> m Int Source #
\(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