Safe Haskell | Safe-Inferred |
---|---|
Language | GHC2021 |
AtCoder.Extra.DynLazySegTree
Description
A dynamic, lazily propagated segment tree that covers a half-open interval [l0,r0). Nodes are instantinated as needed, with the required capacity being approximately 4qlog2L, where q is the number of mutable operations and L is the length of the interval.
Example
>>>
import AtCoder.Extra.DynLazySegTree qualified as Seg
>>>
import AtCoder.Extra.Monoid.Affine1 (Affine1 (..))
>>>
import AtCoder.Extra.Monoid.Affine1 qualified as Affine1
>>>
import Data.Semigroup (Sum (..))
>>>
import Data.Vector.Unboxed qualified as VU
Create a DynLazySegTree
over [0,4) with some initial capacity:
>>>
let len = 4; q = 3
>>>
seg <- Seg.new @_ @(Affine1 Int) @(Sum Int) (Seg.recommendedCapacity len q) 0 4
Different from the LazySegTree
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 3
Sum {getSum = 30}
>>>
-- [0, 10, 20, 0] -> [0, 21, 41, 1]
>>>
Seg.applyIn seg root 1 4 $ Affine1.new 2 1
>>>
Seg.maxRight seg root (<= (Sum 62))
3
If multiple tree roots are allocated, copyInterval
and copyIntervalWith
can be used.
Since: 1.2.1.0
Synopsis
- data DynLazySegTree s f a = DynLazySegTree {}
- class Monoid f => SegAct f a where
- segAct :: f -> a -> a
- segActWithLength :: Int -> f -> a -> a
- newtype Index = Index {}
- new :: (HasCallStack, PrimMonad m, Monoid f, Unbox f, Monoid a, Unbox a) => Int -> Int -> Int -> m (DynLazySegTree (PrimState m) f a)
- buildWith :: (HasCallStack, PrimMonad m, Monoid f, Unbox f, Monoid a, Unbox a) => Int -> Int -> Int -> (Int -> Int -> a) -> m (DynLazySegTree (PrimState m) f a)
- recommendedCapacity :: Int -> Int -> Int
- newRoot :: (HasCallStack, PrimMonad m, Monoid f, Unbox f, Monoid a, Unbox a) => DynLazySegTree (PrimState m) f a -> m Index
- newSeq :: (HasCallStack, PrimMonad m, Monoid f, Unbox f, Monoid a, Unbox a) => DynLazySegTree (PrimState m) f a -> Vector a -> m Index
- write :: (HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a) => DynLazySegTree (PrimState m) f a -> Index -> Int -> a -> m ()
- modify :: (HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a) => DynLazySegTree (PrimState m) f a -> Index -> (a -> a) -> Int -> m ()
- modifyM :: (HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a) => DynLazySegTree (PrimState m) f a -> Index -> (a -> m a) -> Int -> m ()
- prod :: (HasCallStack, PrimMonad m, SegAct f a, Monoid f, Unbox f, Monoid a, Unbox a) => DynLazySegTree (PrimState m) f a -> Index -> Int -> Int -> m a
- allProd :: (HasCallStack, PrimMonad m, SegAct f a, Monoid f, Unbox f, Monoid a, Unbox a) => DynLazySegTree (PrimState m) f a -> Index -> m a
- applyAt :: (HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a) => DynLazySegTree (PrimState m) f a -> Index -> Int -> f -> m ()
- applyIn :: (HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a) => DynLazySegTree (PrimState m) f a -> Index -> Int -> Int -> f -> m ()
- applyAll :: (HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a) => DynLazySegTree (PrimState m) f a -> Index -> f -> m ()
- copyInterval :: (HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a) => DynLazySegTree (PrimState m) f a -> Index -> Index -> Int -> Int -> m ()
- copyIntervalWith :: (HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a) => DynLazySegTree (PrimState m) f a -> Index -> Index -> Int -> Int -> f -> m ()
- resetInterval :: (HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a) => DynLazySegTree (PrimState m) f a -> Index -> Int -> Int -> m ()
- maxRight :: (HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a) => DynLazySegTree (PrimState m) f a -> Index -> (a -> Bool) -> m Int
- maxRightM :: (HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a) => DynLazySegTree (PrimState m) f a -> Index -> (a -> m Bool) -> m Int
- clear :: PrimMonad m => DynLazySegTree (PrimState m) f a -> m ()
Dynamic, lazily propagated segment tree
data DynLazySegTree s f a Source #
A dynamic, lazily propagated segment tree that covers a half-open interval [l0,r0). The nodes are instantinated as needed.
Since: 1.2.1.0
Constructors
DynLazySegTree | |
Fields
|
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 (stimes len a) =stimes
len (segAct
f 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 DerivingStrategies #-} {-# 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) (V2 a) Source # | Since: 1.2.2.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)) (V2 a) Source # | Since: 1.2.2.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 |
Strongly typed index of pool items. User has to explicitly corece
on raw index use.
Instances
Constructors
Arguments
:: (HasCallStack, PrimMonad m, Monoid f, Unbox f, Monoid a, Unbox a) | |
=> Int | Capacity n |
-> Int | Left index boundary l0 |
-> Int | Right index boundary r0 |
-> m (DynLazySegTree (PrimState m) f a) | Dynamic, lazily propagated segment tree |
O(n) Creates a DynLazySegTree
of capacity n for interval [l0,r0) with mempty
as initial leaf values.
Since: 1.2.1.0
Arguments
:: (HasCallStack, PrimMonad m, Monoid f, Unbox f, Monoid a, Unbox a) | |
=> Int | Capacity n |
-> Int | Left index boundary l0 |
-> Int | Right index boundary r0 |
-> (Int -> Int -> a) | Initial monoid value assignment g:(l,r)→a |
-> m (DynLazySegTree (PrimState m) f a) | Dynamic, lazily propagated segment tree |
O(n) Creates a DynLazySegTree
of capacity n for interval [l0,r0) 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 4qlog2L.
Since: 1.2.1.0
newRoot :: (HasCallStack, PrimMonad m, Monoid f, Unbox f, Monoid a, Unbox a) => DynLazySegTree (PrimState m) f a -> m Index Source #
O(1) Creates a new root in [l0,r0).
Since: 1.2.1.0
newSeq :: (HasCallStack, PrimMonad m, Monoid f, Unbox f, Monoid a, Unbox a) => DynLazySegTree (PrimState m) f 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
- [l0,r0)=[0,L): The index boundary of the segment tree must match the sequence.
Since: 1.2.1.0
Accessing elements
write :: (HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a) => DynLazySegTree (PrimState m) f a -> Index -> Int -> a -> m () Source #
O(logL) Writes to the monoid value of the node at i.
Constraints
- l0≤i<r0
Since: 1.2.1.0
modify :: (HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a) => DynLazySegTree (PrimState m) f a -> Index -> (a -> a) -> Int -> m () Source #
O(logL) Modifies the monoid value of the node at i.
Constraints
- l0≤i<r0
Since: 1.2.1.0
modifyM :: (HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a) => DynLazySegTree (PrimState m) f a -> Index -> (a -> m a) -> Int -> m () Source #
O(logL) Modifies the monoid value of the node at i.
Constraints
- l0≤i<r0
Since: 1.2.1.0
Products
prod :: (HasCallStack, PrimMonad m, SegAct f a, Monoid f, Unbox f, Monoid a, Unbox a) => DynLazySegTree (PrimState m) f a -> Index -> Int -> Int -> m a Source #
O(logL) Returns the monoid product in [l,r).
Constraints
- l0≤l≤r≤r0
Since: 1.2.1.0
allProd :: (HasCallStack, PrimMonad m, SegAct f a, Monoid f, Unbox f, Monoid a, Unbox a) => DynLazySegTree (PrimState m) f a -> Index -> m a Source #
O(logL) Returns the monoid product in [l0,r0).
Since: 1.2.1.0
Applications
applyAt :: (HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a) => DynLazySegTree (PrimState m) f a -> Index -> Int -> f -> m () Source #
O(logL) Applies a monoid action f to the node at index i.
Constraints
- l0≤i<r0
- The root is not null
Since: 1.2.1.0
applyIn :: (HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a) => DynLazySegTree (PrimState m) f a -> Index -> Int -> Int -> f -> m () Source #
O(logL) Applies a monoid action f to an interval [l,r).
Constraints
- l0≤l≤r≤r0
- The root is not null
Since: 1.2.1.0
applyAll :: (HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a) => DynLazySegTree (PrimState m) f a -> Index -> f -> m () Source #
O(logL) Applies a monoid action f to the interval [l0,r0).
Since: 1.2.1.0
Tree operations
copyInterval :: (HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a) => DynLazySegTree (PrimState m) f a -> Index -> Index -> Int -> Int -> m () Source #
O(logL) Given two trees a and b, copies b[l,r) to a[l,r).
Constraints
- l0≤l≤r≤r0
- The root is not null
Since: 1.2.1.0
copyIntervalWith :: (HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a) => DynLazySegTree (PrimState m) f a -> Index -> Index -> Int -> Int -> f -> m () Source #
O(logL) Given two trees a and b, copies b[l,r) to a[l,r), applying a monoid action f.
Constraints
- l0≤l≤r≤r0
- The root is not null
Since: 1.2.1.0
resetInterval :: (HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a) => DynLazySegTree (PrimState m) f a -> Index -> Int -> Int -> m () Source #
O(logL) Resets an interval [l,r) to initial monoid values.
Constraints
- l0≤l≤r≤r0
Since: 1.2.1.0
Binary searches
maxRight :: (HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a) => DynLazySegTree (PrimState m) f a -> Index -> (a -> Bool) -> m Int Source #
O(logL) Returns the maximum r∈[l0,r0) where f(al0al0+1…ar−1) holds.
Since: 1.2.1.0
maxRightM :: (HasCallStack, PrimMonad m, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a) => DynLazySegTree (PrimState m) f a -> Index -> (a -> m Bool) -> m Int Source #
O(logL) Returns the maximum r∈[l0,r0) where f(al0al0+1…ar−1) holds.
Since: 1.2.1.0