Safe Haskell | Safe-Inferred |
---|---|
Language | GHC2021 |
AtCoder.Extra.Seq.Map
Description
Key-value pairs with monoid products and monoid actions on them through the SegAct
instance.
Performance
This module is extremely slow as an ordinary map. Do not use it unless you need monoid products.
Example
>>>
import AtCoder.Extra.Monoid.RangeAdd qualified as RangeAdd
>>>
import AtCoder.Extra.Seq.Map qualified as M
>>>
import Data.Semigroup (Sum (..))
>>>
import Data.Vector.Unboxed qualified as VU
>>>
m <- M.new @_ @(RangeAdd.RangeAdd (Sum Int)) @Int @(Sum Int) 10
>>>
M.insert m 1 10
>>>
M.insert m 3 30
>>>
M.prod m 1 2
Sum {getSum = 10}
Since: 1.2.1.0
Synopsis
- data Map s f k v = Map {}
- class Monoid f => SegAct f a where
- segAct :: f -> a -> a
- segActWithLength :: Int -> f -> a -> a
- new :: (PrimMonad m, Monoid f, Unbox f, Unbox k, Unbox v, Monoid v) => Int -> m (Map (PrimState m) f k v)
- build :: (HasCallStack, PrimMonad m, Monoid f, Unbox f, Ord k, Unbox k, Unbox v, Monoid v) => Int -> Vector (k, v) -> m (Map (PrimState m) f k v)
- reset :: (PrimMonad m, Monoid f, Unbox f, Unbox k, Unbox v, Monoid v) => Map (PrimState m) f k v -> m ()
- capacity :: Map s f k v -> Int
- size :: PrimMonad m => Map (PrimState m) f k v -> m Int
- member :: (HasCallStack, PrimMonad m, Eq f, Monoid f, Unbox f, Ord k, Unbox k, Monoid v, Unbox v, SegAct f v) => Map (PrimState m) f k v -> k -> m Bool
- lookup :: (HasCallStack, PrimMonad m, Eq f, Monoid f, Unbox f, Ord k, Unbox k, Monoid v, Unbox v, SegAct f v) => Map (PrimState m) f k v -> k -> m (Maybe v)
- adjust :: (HasCallStack, PrimMonad m, Eq f, Monoid f, Unbox f, Ord k, Unbox k, Monoid v, Unbox v, SegAct f v) => Map (PrimState m) f k v -> (v -> v) -> k -> m ()
- insert :: (HasCallStack, PrimMonad m, Eq f, Monoid f, Unbox f, Ord k, Unbox k, Monoid v, Unbox v, SegAct f v) => Map (PrimState m) f k v -> k -> v -> m ()
- insertWith :: (HasCallStack, PrimMonad m, Eq f, Monoid f, Unbox f, Ord k, Unbox k, Monoid v, Unbox v, SegAct f v) => Map (PrimState m) f k v -> (v -> v -> v) -> k -> v -> m ()
- delete :: (HasCallStack, PrimMonad m, Eq f, Monoid f, Unbox f, Ord k, Unbox k, Monoid v, Unbox v, SegAct f v) => Map (PrimState m) f k v -> k -> m (Maybe v)
- delete_ :: (HasCallStack, PrimMonad m, Eq f, Monoid f, Unbox f, Ord k, Unbox k, Monoid v, Unbox v, SegAct f v) => Map (PrimState m) f k v -> k -> m ()
- prod :: (HasCallStack, PrimMonad m, Eq f, Monoid f, Unbox f, Ord k, Unbox k, Monoid v, Unbox v, SegAct f v) => Map (PrimState m) f k v -> k -> k -> m v
- prodMaybe :: (HasCallStack, PrimMonad m, Eq f, Monoid f, Unbox f, Ord k, Unbox k, Monoid v, Unbox v, SegAct f v) => Map (PrimState m) f k v -> k -> k -> m (Maybe v)
- allProd :: (HasCallStack, PrimMonad m, Eq f, Monoid f, Unbox f, Ord k, Unbox k, Monoid v, Unbox v, SegAct f v) => Map (PrimState m) f k v -> m v
- applyIn :: (HasCallStack, PrimMonad m, Eq f, Monoid f, Unbox f, Ord k, Unbox k, Monoid v, Unbox v, SegAct f v) => Map (PrimState m) f k v -> k -> k -> f -> m ()
- applyAll :: (HasCallStack, PrimMonad m, Eq f, Monoid f, Unbox f, Ord k, Unbox k, Monoid v, Unbox v, SegAct f v) => Map (PrimState m) f k v -> f -> m ()
- lookupLE :: (HasCallStack, PrimMonad m, Eq f, Monoid f, Unbox f, Ord k, Unbox k, Monoid v, Unbox v, SegAct f v) => Map (PrimState m) f k v -> k -> m (Maybe (k, v))
- lookupLT :: (HasCallStack, PrimMonad m, Eq f, Monoid f, Unbox f, Ord k, Unbox k, Monoid v, Unbox v, SegAct f v) => Map (PrimState m) f k v -> k -> m (Maybe (k, v))
- lookupGE :: (HasCallStack, PrimMonad m, Eq f, Monoid f, Unbox f, Ord k, Unbox k, Monoid v, Unbox v, SegAct f v) => Map (PrimState m) f k v -> k -> m (Maybe (k, v))
- lookupGT :: (HasCallStack, PrimMonad m, Eq f, Monoid f, Unbox f, Ord k, Unbox k, Monoid v, Unbox v, SegAct f v) => Map (PrimState m) f k v -> k -> m (Maybe (k, v))
- readAt :: (HasCallStack, PrimMonad m, Eq f, Monoid f, Unbox f, Monoid v, Unbox v, SegAct f v) => Map (PrimState m) f k v -> Int -> m v
- readMaybeAt :: (HasCallStack, PrimMonad m, Eq f, Monoid f, Unbox f, Monoid v, Unbox v, SegAct f v) => Map (PrimState m) f k v -> Int -> m (Maybe v)
- writeAt :: (HasCallStack, PrimMonad m, Eq f, Monoid f, Unbox f, Monoid v, Unbox v, SegAct f v) => Map (PrimState m) f k v -> Int -> v -> m ()
- modifyAt :: (HasCallStack, PrimMonad m, Eq f, Monoid f, Unbox f, Monoid v, Unbox v, SegAct f v) => Map (PrimState m) f k v -> (v -> v) -> Int -> m ()
- exchangeAt :: (HasCallStack, PrimMonad m, Eq f, Monoid f, Unbox f, Monoid v, Unbox v, SegAct f v) => Map (PrimState m) f k v -> Int -> v -> m v
- prodInInterval :: (HasCallStack, PrimMonad m, Eq f, Monoid f, Unbox f, Monoid v, Unbox v, SegAct f v) => Map (PrimState m) f k v -> Int -> Int -> m v
- applyInInterval :: (HasCallStack, PrimMonad m, Eq f, Monoid f, Unbox f, Monoid v, Unbox v, SegAct f v) => Map (PrimState m) f k v -> Int -> Int -> f -> m ()
- ilowerBound :: (HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a) => Map (PrimState m) f k a -> (Int -> a -> Bool) -> m Int
- ilowerBoundM :: (HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a) => Map (PrimState m) f k a -> (Int -> a -> m Bool) -> m Int
- ilowerBoundProd :: (HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a) => Map (PrimState m) f k a -> (Int -> a -> Bool) -> m Int
- ilowerBoundProdM :: (HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a) => Map (PrimState m) f k a -> (Int -> a -> m Bool) -> m Int
- freeze :: (HasCallStack, PrimMonad m, Eq f, Monoid f, Unbox f, Ord k, Unbox k, Monoid v, Unbox v, SegAct f v) => Map (PrimState m) f k v -> m (Vector (k, v))
Map
Key-value pairs with monoid products and monoid actions on them through the SegAct
instance.
Since: 1.2.1.0
Re-exports
class Monoid f => SegAct f a where Source #
Typeclass reprentation of the LazySegTree
properties. User can implement either segAct
or
segActWithLength
.
Instances should satisfy the follwing properties:
- Left monoid action
segAct
(f2<>
f1) x =segAct
f2 (segAct
f1 x)- Identity map
segAct
mempty
x = x- Endomorphism
segAct
f (x1<>
x2) = (segAct
f x1)<>
(segAct
f x2)
If you implement SegAct
via segActWithLength
, satisfy one more propety:
- Linear left monoid action
.segActWithLength
len f a =stimes
len (segAct
f a) a
Invariant
In SegAct
instances, new semigroup values are always given from the left: new
. The
order is important for non-commutative monoid implementations.<>
old
Example instance
Take Affine1
as an example of type \(F\).
{-# LANGUAGE TypeFamilies #-} import AtCoder.LazySegTree qualified as LST import AtCoder.LazySegTree (SegAct (..)) import Data.Monoid import Data.Vector.Generic qualified as VG import Data.Vector.Generic.Mutable qualified as VGM import Data.Vector.Unboxed qualified as VU import Data.Vector.Unboxed.Mutable qualified as VUM -- | f x = a * x + b. It's implemented as a newtype of `(a, a)` for easyUnbox
deriving. newtypeAffine1
a =Affine1
(Affine1
a) deriving newtype (Eq
,Ord
,Show
) -- | This type alias makes theUnbox
deriving easier, described velow. typeAffine1Repr
a = (a, a) instance (Num
a) =>Semigroup
(Affine1
a) where {-# INLINE (<>
) #-} (Affine1
(!a1, !b1))<>
(Affine1
(!a2, !b2)) =Affine1
(a1 * a2, a1 * b2 + b1) instance (Num
a) =>Monoid
(Affine1
a) where {-# INLINEmempty
#-}mempty
=Affine1
(1, 0) instance (Num
a) =>SegAct
(Affine1
a) (Sum
a) where {-# INLINE segActWithLength #-}segActWithLength
len (Affine1
(!a, !b)) !x = a * x + b * fromIntegral len
Deriving Unbox
is very easy for such a newtype (though the efficiency is
not the maximum):
newtype instance VU.MVector s (Affine1
a) = MV_Affine1 (VU.MVector s (Affine1
a)) newtype instance VU.Vector (Affine1
a) = V_Affine1 (VU.Vector (Affine1
a)) deriving instance (VU.Unbox a) => VGM.MVector VUM.MVector (Affine1
a) deriving instance (VU.Unbox a) => VG.Vector VU.Vector (Affine1
a) instance (VU.Unbox a) => VU.Unbox (Affine1
a)
Example contest template
Define your monoid action F
and your acted monoid X
:
{-# LANGUAGE TypeFamilies #-} import AtCoder.LazySegTree qualified as LST import AtCoder.LazySegTree (SegAct (..)) import Data.Vector.Generic qualified as VG import Data.Vector.Generic.Mutable qualified as VGM import Data.Vector.Unboxed qualified as VU import Data.Vector.Unboxed.Mutable qualified as VUM {- ORMOLU_DISABLE -} -- |F
is a custom monoid action, defined as a newtype ofFRepr
. newtype F = F FRepr deriving newtype (Eq, Ord, Show) ; unF :: F -> FRepr ; unF (F x) = x ; newtype instance VU.MVector s F = MV_F (VU.MVector s FRepr) ; newtype instance VU.Vector F = V_F (VU.Vector FRepr) ; deriving instance VGM.MVector VUM.MVector F ; deriving instance VG.Vector VU.Vector F ; instance VU.Unbox F ; {- ORMOLU_ENABLE -} -- | Affine: f x = a * x + b type FRepr = (Int, Int) instance Semigroup F where --new <> old
{-# INLINE (<>) #-} (F (!a1, !b1)) <> (F (!a2, !b2)) = F (a1 * a2, a1 * b2 + b1) instance Monoid F where {-# INLINE mempty #-} mempty = F (1, 0) {- ORMOLU_DISABLE -} -- |X
is a custom acted monoid, defined as a newtype ofXRepr
. newtype X = X XRepr deriving newtype (Eq, Ord, Show) ; unX :: X -> XRepr ; unX (X x) = x; newtype instance VU.MVector s X = MV_X (VU.MVector s XRepr) ; newtype instance VU.Vector X = V_X (VU.Vector XRepr) ; deriving instance VGM.MVector VUM.MVector X ; deriving instance VG.Vector VU.Vector X ; instance VU.Unbox X ; {- ORMOLU_ENABLE -} -- | ActedInt
(same as `Sum Int`). type XRepr = Int deriving instance Num X; -- in our caseX
is aNum
. instance Semigroup X where {-# INLINE (<>) #-} (X x1) <> (X x2) = X $! x1 + x2 instance Monoid X where {-# INLINE mempty #-} mempty = X 0 instance SegAct F X where -- {-# INLINE segAct #-} -- segAct len (F (!a, !b)) (X x) = X $! a * x + b {-# INLINE segActWithLength #-} segActWithLength len (F (!a, !b)) (X x) = X $! a * x + len * b
It's tested as below:
expect :: (Eq a, Show a) => String -> a -> a -> ()
expect msg a b
| a == b = ()
| otherwise = error $ msg ++ ": expected " ++ show a ++ ", found " ++ show b
main :: IO ()
main = do
seg <- LST.build _
F @X $ VU.map X $ VU.fromList [1, 2, 3, 4]
LST.applyIn seg 1 3 $ F (2, 1) -- [1, 5, 7, 4]
LST.write seg 3 $ X 10 -- [1, 5, 7, 10]
LST.modify seg (+ (X 1)) 0 -- [2, 5, 7, 10]
!_ <- (expect "test 1" (X 5)) <$> LST.read seg 1
!_ <- (expect "test 2" (X 14)) <$> LST.prod seg 0 3 -- reads an interval [0, 3)
!_ <- (expect "test 3" (X 24)) <$> LST.allProd seg
!_ <- (expect "test 4" 2) <$> LST.maxRight seg 0 (<= (X 10)) -- sum [0, 2) = 7 <= 10
!_ <- (expect "test 5" 3) <$> LST.minLeft seg 4 (<= (X 10)) -- sum [3, 4) = 10 <= 10
putStrLn "=> test passed!"
Since: 1.0.0.0
Minimal complete definition
Nothing
Methods
segAct :: f -> a -> a Source #
Lazy segment tree action \(f(x)\).
Since: 1.0.0.0
segActWithLength :: Int -> f -> a -> a Source #
Lazy segment tree action \(f(x)\) with the target monoid's length.
If you implement SegAct
with this function, you don't have to store the monoid's length,
since it's given externally.
Since: 1.0.0.0
Instances
SegAct () a Source # | Since: 1.2.0.0 |
Defined in AtCoder.LazySegTree | |
Monoid a => SegAct (RangeSet a) a Source # | Since: 1.0.0.0 |
Defined in AtCoder.Extra.Monoid.RangeSet | |
Num a => SegAct (Affine1 (Sum a)) (Sum a) Source # | Since: 1.0.0.0 |
Num a => SegAct (Affine1 a) (Sum a) Source # | Since: 1.0.0.0 |
Num a => SegAct (Mat2x2 a) (V2 a) Source # | Since: 1.1.0.0 |
(Num a, Monoid (Max a)) => SegAct (RangeAdd (Max a)) (Max a) Source # | Since: 1.1.0.0 |
(Num a, Monoid (Min a)) => SegAct (RangeAdd (Min a)) (Min a) Source # | Since: 1.1.0.0 |
Num a => SegAct (RangeAdd (Sum a)) (Sum a) Source # | Since: 1.2.0.0 |
Num a => SegAct (Dual (Affine1 (Sum a))) (Sum a) Source # | Since: 1.0.0.0 |
Num a => SegAct (Dual (Affine1 a)) (Sum a) Source # | Since: 1.0.0.0 |
Num a => SegAct (Dual (Mat2x2 a)) (V2 a) Source # | Since: 1.1.0.0 |
Constructors
new :: (PrimMonad m, Monoid f, Unbox f, Unbox k, Unbox v, Monoid v) => Int -> m (Map (PrimState m) f k v) Source #
build :: (HasCallStack, PrimMonad m, Monoid f, Unbox f, Ord k, Unbox k, Unbox v, Monoid v) => Int -> Vector (k, v) -> m (Map (PrimState m) f k v) Source #
reset :: (PrimMonad m, Monoid f, Unbox f, Unbox k, Unbox v, Monoid v) => Map (PrimState m) f k v -> m () Source #
\(O(1)\) Clears the map. All the handles must not be used again.
Since: 1.2.1.0
Metadata
capacity :: Map s f k v -> Int Source #
\(O(1)\) Returns the maximum number of elements the map can store.
Since: 1.2.1.0
size :: PrimMonad m => Map (PrimState m) f k v -> m Int Source #
\(O(1)\) Returns the number of elements in the map.
Since: 1.2.1.0
Key-based operations
Read/write
member :: (HasCallStack, PrimMonad m, Eq f, Monoid f, Unbox f, Ord k, Unbox k, Monoid v, Unbox v, SegAct f v) => Map (PrimState m) f k v -> k -> m Bool Source #
Amoritzed \(O(\log n)\). Returns whether a node with key \(k\) is in the map.
Since: 1.2.1.0
lookup :: (HasCallStack, PrimMonad m, Eq f, Monoid f, Unbox f, Ord k, Unbox k, Monoid v, Unbox v, SegAct f v) => Map (PrimState m) f k v -> k -> m (Maybe v) Source #
Amortized \(O(\log n)\). Looks up for the monoid value of a node with key \(k\).
Since: 1.2.1.0
adjust :: (HasCallStack, PrimMonad m, Eq f, Monoid f, Unbox f, Ord k, Unbox k, Monoid v, Unbox v, SegAct f v) => Map (PrimState m) f k v -> (v -> v) -> k -> m () Source #
Amoritzed \(O(\log n)\). Adjusts the monoid value of a node with key \(k\).
Since: 1.2.1.0
Insert/delete
insert :: (HasCallStack, PrimMonad m, Eq f, Monoid f, Unbox f, Ord k, Unbox k, Monoid v, Unbox v, SegAct f v) => Map (PrimState m) f k v -> k -> v -> m () Source #
Amortized \(O(\log n)\). Inserts a \((k, v)\) pair. If the key is already present in the map, the associated value is replaced with the supplied value.
Since: 1.2.1.0
Arguments
:: (HasCallStack, PrimMonad m, Eq f, Monoid f, Unbox f, Ord k, Unbox k, Monoid v, Unbox v, SegAct f v) | |
=> Map (PrimState m) f k v | Map |
-> (v -> v -> v) | new -> old -> combined |
-> k | Key |
-> v | Value |
-> m () |
Amortized \(O(\log n)\). Inserts a \((k, v)\) pairs, combining new value and old value.
Since: 1.2.1.0
delete :: (HasCallStack, PrimMonad m, Eq f, Monoid f, Unbox f, Ord k, Unbox k, Monoid v, Unbox v, SegAct f v) => Map (PrimState m) f k v -> k -> m (Maybe v) Source #
Amortized \(O(\log n)\). Deletes an element with key \(k\).
Since: 1.2.1.0
delete_ :: (HasCallStack, PrimMonad m, Eq f, Monoid f, Unbox f, Ord k, Unbox k, Monoid v, Unbox v, SegAct f v) => Map (PrimState m) f k v -> k -> m () Source #
Amortized \(O(\log n)\). Deletes an element with key \(k\).
Since: 1.2.1.0
Products
prod :: (HasCallStack, PrimMonad m, Eq f, Monoid f, Unbox f, Ord k, Unbox k, Monoid v, Unbox v, SegAct f v) => Map (PrimState m) f k v -> k -> k -> m v Source #
Amortized \(O(\log n)\). Returns the monoid product in an interval \([k_1, k_2)\). Throws an error for \(k_1 \gt k_2\).
Constraints
- \(k_1 \le k_2\)
Since: 1.2.1.0
prodMaybe :: (HasCallStack, PrimMonad m, Eq f, Monoid f, Unbox f, Ord k, Unbox k, Monoid v, Unbox v, SegAct f v) => Map (PrimState m) f k v -> k -> k -> m (Maybe v) Source #
Amortized \(O(\log n)\). Returns the monoid product in an interval \([k_1, k_2)\). Returns
Nothing
if an invalid interval is given or for an empty sequence.
Since: 1.2.1.0
allProd :: (HasCallStack, PrimMonad m, Eq f, Monoid f, Unbox f, Ord k, Unbox k, Monoid v, Unbox v, SegAct f v) => Map (PrimState m) f k v -> m v Source #
Amortized \(O(\log n)\). Returns the monoid product in an interval \([k_1, k_2)\). Returns
Nothing
if an invalid interval is given or for an empty sequence.
Since: 1.2.1.0
Applications
applyIn :: (HasCallStack, PrimMonad m, Eq f, Monoid f, Unbox f, Ord k, Unbox k, Monoid v, Unbox v, SegAct f v) => Map (PrimState m) f k v -> k -> k -> f -> m () Source #
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.1.0
applyAll :: (HasCallStack, PrimMonad m, Eq f, Monoid f, Unbox f, Ord k, Unbox k, Monoid v, Unbox v, SegAct f v) => Map (PrimState m) f k v -> f -> m () Source #
Amortized \(O(\log n)\).
Since: 1.2.1.0
Bisection methods
lookupLE :: (HasCallStack, PrimMonad m, Eq f, Monoid f, Unbox f, Ord k, Unbox k, Monoid v, Unbox v, SegAct f v) => Map (PrimState m) f k v -> k -> m (Maybe (k, v)) Source #
Amortized \(O(\log n)\). Looks up for \((k, v)\) pair with the maximum key \(k\) such that \(k \le k_{\mathrm{ref}}\).
Since: 1.2.1.0
lookupLT :: (HasCallStack, PrimMonad m, Eq f, Monoid f, Unbox f, Ord k, Unbox k, Monoid v, Unbox v, SegAct f v) => Map (PrimState m) f k v -> k -> m (Maybe (k, v)) Source #
Amortized \(O(\log n)\). Looks up for \((k, v)\) pair with the maximum key \(k\) such that \(k \lt k_{\mathrm{ref}}\).
Since: 1.2.1.0
lookupGE :: (HasCallStack, PrimMonad m, Eq f, Monoid f, Unbox f, Ord k, Unbox k, Monoid v, Unbox v, SegAct f v) => Map (PrimState m) f k v -> k -> m (Maybe (k, v)) Source #
Amortized \(O(\log n)\). Looks up for \((k, v)\) pair with the minimum key \(k\) such that \(k \ge k_{\mathrm{ref}}\).
Since: 1.2.1.0
lookupGT :: (HasCallStack, PrimMonad m, Eq f, Monoid f, Unbox f, Ord k, Unbox k, Monoid v, Unbox v, SegAct f v) => Map (PrimState m) f k v -> k -> m (Maybe (k, v)) Source #
Amortized \(O(\log n)\). Looks up for \((k, v)\) pair with the minimum key \(k\) such that \(k \gt k_{\mathrm{ref}}\).
Since: 1.2.1.0
Index-based operations
Read/write
readAt :: (HasCallStack, PrimMonad m, Eq f, Monoid f, Unbox f, Monoid v, Unbox v, SegAct f v) => Map (PrimState m) f k v -> Int -> m v Source #
Amortized \(O(\log n)\).
Since: 1.2.1.0
readMaybeAt :: (HasCallStack, PrimMonad m, Eq f, Monoid f, Unbox f, Monoid v, Unbox v, SegAct f v) => Map (PrimState m) f k v -> Int -> m (Maybe v) Source #
Amortized \(O(\log n)\).
Since: 1.2.1.0
writeAt :: (HasCallStack, PrimMonad m, Eq f, Monoid f, Unbox f, Monoid v, Unbox v, SegAct f v) => Map (PrimState m) f k v -> Int -> v -> m () Source #
Amortized \(O(\log n)\).
Since: 1.2.1.0
modifyAt :: (HasCallStack, PrimMonad m, Eq f, Monoid f, Unbox f, Monoid v, Unbox v, SegAct f v) => Map (PrimState m) f k v -> (v -> v) -> Int -> m () Source #
Amortized \(O(\log n)\).
Since: 1.2.1.0
exchangeAt :: (HasCallStack, PrimMonad m, Eq f, Monoid f, Unbox f, Monoid v, Unbox v, SegAct f v) => Map (PrimState m) f k v -> Int -> v -> m v Source #
Amortized \(O(\log n)\).
Since: 1.2.1.0
Products
prodInInterval :: (HasCallStack, PrimMonad m, Eq f, Monoid f, Unbox f, Monoid v, Unbox v, SegAct f v) => Map (PrimState m) f k v -> Int -> Int -> m v Source #
Amortized \(O(\log n)\).
Since: 1.2.1.0
Applications
applyInInterval :: (HasCallStack, PrimMonad m, Eq f, Monoid f, Unbox f, Monoid v, Unbox v, SegAct f v) => Map (PrimState m) f k v -> Int -> Int -> f -> m () Source #
Amortized \(O(\log n)\).
Since: 1.2.1.0
Bisection methods
Arguments
:: (HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a) | |
=> Map (PrimState m) f k a | Map |
-> (Int -> a -> Bool) | User predicate \(f(i, v_i)\) that takes the index and the monoid value |
-> m Int | Maximum \(r\), where \(f(i, v_i)\) holds for \(i \in [0, r)\) |
Amortized \(O(\log n)\).
Since: 1.2.1.0
Arguments
:: (HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a) | |
=> Map (PrimState m) f k a | Map |
-> (Int -> a -> m Bool) | User predicate \(f(i, v_i)\) that takes the index and the monoid value |
-> m Int | Maximum \(r\), where \(f(i, v_i)\) holds for \(i \in [0, r)\) |
Amortized \(O(\log n)\).
Since: 1.2.1.0
Arguments
:: (HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a) | |
=> Map (PrimState m) f k a | Map |
-> (Int -> a -> Bool) | User predicate \(f(i, v_0 \dots v_i)\) that takes the index and the monoid product |
-> m Int | Maximum \(r\), where \(f(i, v_0 \dots v_i)\) holds for \(i \in [0, r)\) |
Amortized \(O(\log n)\).
Since: 1.2.1.0
Arguments
:: (HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a) | |
=> Map (PrimState m) f k a | Map |
-> (Int -> a -> m Bool) | User predicate \(f(i, v_0 \dots v_i)\) that takes the index and the monoid product |
-> m Int | Maximum \(r\), where \(f(i, v_0 \dots v_i)\) holds for \(i \in [0, r)\) |
Amortized \(O(\log n)\).
Since: 1.2.1.0