| Safe Haskell | Safe-Inferred |
|---|---|
| Language | GHC2021 |
AtCoder.LazySegTree
Description
A lazily propagted segment tree. It is the data structure for the pair of a monoid \((S, \cdot: S \times S \to S, e \in S)\) and a set \(F\) of \(S \to S\) mappings that satisfies the following properties.
- \(F\) contains the identity map \(\mathrm{id}\) such that \(\mathrm{id}(x) = x\) holds for all \(x \in S\).
- \(F\) is closed under composition, i.e., \(f \circ g \in F\) holds for all \(f, g \in F\).
- \(f(x \cdot y) = f(x) \cdot f(y)\) holds for all \(f \in F\) and \(x, y \in S\).
Given an array \(S\) of length \(N\), it processes the following queries in \(O(\log N)\) time.
- Acting the map \(f\in F\) (cf. \(x = f(x)\)) on all the elements of an interval
- Calculating the product of the elements of an interval
In Haskell types, \(F\) is a SegAct () and \(S\) is a segAct fMonoid. For simplicity, in
this document, we assume that the relevant methods work in constant time. If these they work in
\(O(T)\) time, each time complexity appear in this document is multipled by \(O(T)\).
Example
Here we'll use Affine1 as a monoid action \(F\) and Sum
as the acted monoid \(S\):
>>>import AtCoder.LazySegTree qualified as LST>>>import AtCoder.Extra.Monoid (SegAct(..), Affine1(..)) -- `SegAct` is also re-exported in Extra.Monoid.>>>import Data.Semigroup (Sum(..))
Use build to construct a LazySegTree with initial values. constructs a
build @_ @f @aLazySegTree of SegAct f a:
>>>seg <- LST.build @_ @(Affine1 Int) @(Sum Int) $ VU.fromList [1, 2, 3, 4]
applyIn seg l r f applies an action \(f\) to an interval \([l, r)\):
>>>LST.applyIn seg 1 3 $ Affine1 (2, 1) -- [1, 5, 7, 4]
Modify one element with write, modify, modifyM or applyAt:
>>>LST.write seg 3 $ Sum 10 -- [1, 5, 7, 10]>>>LST.modify seg (+ 1) 0 -- [2, 5, 7, 10]
Read the values with read, prod or allProd:
>>>LST.read seg 1Sum {getSum = 5}
>>>LST.prod seg 0 3 -- product (fold) of `Sum Int` in interval [0, 3)Sum {getSum = 14}
>>>LST.allProd segSum {getSum = 24}
Run binary search:
>>>LST.maxRight seg 0 (<= (Sum 10)) -- sum [0, 2) = 7 <= 102
>>>LST.minLeft seg 4 (<= (Sum 10)) -- sum [3, 4) = 10 <= 103
Inspect all the values in \(O(n \log n)\) with freeze or unsafeFreeze:
>>>VU.map getSum <$> LST.freeze seg[2,5,7,10]
Tips
prodreturns \(a_l \cdot a_{l + 1} \cdot .. \cdot a_{r - 1}\). If you need \(a_{r - 1} \cdot a_{r - 2} \cdot .. \cdot a_{l}\), wrap your monoid inDual.- If you ever need to store boxed types to
LazySegTree, wrap it inData.Vector.Unboxed.DoNotUnboxStrictor the like.
Major changes from the original ac-library
- The API is based on
MonoidandSegAct, not the functionsop,e,mapping,compositionandid. getandsetare renamed toreadandwrite.modify,modifyM,exchange,freezeandunsafeFreezeare added.
Since: 1.0.0.0
Synopsis
- class Monoid f => SegAct f a where
- segAct :: f -> a -> a
- segActWithLength :: Int -> f -> a -> a
- data LazySegTree s f a
- new :: (HasCallStack, PrimMonad m, Monoid f, Unbox f, Monoid a, Unbox a) => Int -> m (LazySegTree (PrimState m) f a)
- build :: (PrimMonad m, Monoid f, Unbox f, Monoid a, Unbox a) => Vector a -> m (LazySegTree (PrimState m) f a)
- write :: (HasCallStack, PrimMonad m, SegAct f a, Unbox f, Monoid a, Unbox a) => LazySegTree (PrimState m) f a -> Int -> a -> m ()
- modify :: (HasCallStack, PrimMonad m, SegAct f a, Unbox f, Monoid a, Unbox a) => LazySegTree (PrimState m) f a -> (a -> a) -> Int -> m ()
- modifyM :: (HasCallStack, PrimMonad m, SegAct f a, Unbox f, Monoid a, Unbox a) => LazySegTree (PrimState m) f a -> (a -> m a) -> Int -> m ()
- exchange :: (HasCallStack, PrimMonad m, SegAct f a, Unbox f, Monoid a, Unbox a) => LazySegTree (PrimState m) f a -> Int -> a -> m a
- read :: (HasCallStack, PrimMonad m, SegAct f a, Unbox f, Monoid a, Unbox a) => LazySegTree (PrimState m) f a -> Int -> m a
- prod :: (HasCallStack, PrimMonad m, SegAct f a, Unbox f, Monoid a, Unbox a) => LazySegTree (PrimState m) f a -> Int -> Int -> m a
- prodMaybe :: (HasCallStack, PrimMonad m, SegAct f a, Unbox f, Monoid a, Unbox a) => LazySegTree (PrimState m) f a -> Int -> Int -> m (Maybe a)
- allProd :: (PrimMonad m, Monoid a, Unbox a) => LazySegTree (PrimState m) f a -> m a
- applyAt :: (HasCallStack, PrimMonad m, SegAct f a, Unbox f, Monoid a, Unbox a) => LazySegTree (PrimState m) f a -> Int -> f -> m ()
- applyIn :: (HasCallStack, PrimMonad m, SegAct f a, Unbox f, Monoid a, Unbox a) => LazySegTree (PrimState m) f a -> Int -> Int -> f -> m ()
- minLeft :: (HasCallStack, PrimMonad m, SegAct f a, Unbox f, Monoid a, Unbox a) => LazySegTree (PrimState m) f a -> Int -> (a -> Bool) -> m Int
- minLeftM :: (HasCallStack, PrimMonad m, SegAct f a, Unbox f, Monoid a, Unbox a) => LazySegTree (PrimState m) f a -> Int -> (a -> m Bool) -> m Int
- maxRight :: (HasCallStack, PrimMonad m, SegAct f a, Unbox f, Monoid a, Unbox a) => LazySegTree (PrimState m) f a -> Int -> (a -> Bool) -> m Int
- maxRightM :: (HasCallStack, PrimMonad m, SegAct f a, Unbox f, Monoid a, Unbox a) => LazySegTree (PrimState m) f a -> Int -> (a -> m Bool) -> m Int
- freeze :: (PrimMonad m, SegAct f a, Unbox f, Monoid a, Unbox a) => LazySegTree (PrimState m) f a -> m (Vector a)
- unsafeFreeze :: (PrimMonad m, SegAct f a, Unbox f, Monoid a, Unbox a) => LazySegTree (PrimState m) f a -> m (Vector a)
Documentation
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 =segActf2 (segActf1 x)- Identity map
segActmemptyx = x- Endomorphism
segActf (x1<>x2) = (segActf x1)<>(segActf x2)
If you implement SegAct via segActWithLength, satisfy one more propety:
- Linear left monoid action
.segActWithLengthlen f a =stimeslen (segActf 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 easy Unbox deriving.
newtype Affine1 a = Affine1 (Affine1 a)
deriving newtype (Eq, Ord, Show)
-- | This type alias makes the Unbox deriving easier, described velow.
type Affine1Repr 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
{-# INLINE mempty #-}
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 (Affine1a) = MV_Affine1 (VU.MVector s (Affine1a)) newtype instance VU.Vector (Affine1a) = V_Affine1 (VU.Vector (Affine1a)) deriving instance (VU.Unbox a) => VGM.MVector VUM.MVector (Affine1a) deriving instance (VU.Unbox a) => VG.Vector VU.Vector (Affine1a) instance (VU.Unbox a) => VU.Unbox (Affine1a)
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 of FRepr.
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 of XRepr.
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 -}
-- | Acted Int (same as `Sum Int`).
type XRepr = Int
deriving instance Num X; -- in our case X is a Num.
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
| 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 |
| Monoid (Max a) => SegAct (RangeAdd (Max a)) (Max a) Source # | Since: 1.1.0.0 |
| Monoid (Min a) => SegAct (RangeAdd (Min a)) (Min a) Source # | Since: 1.1.0.0 |
| Monoid (Sum a) => SegAct (RangeAdd (Sum a)) (Sum a) Source # | Since: 1.1.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 |
data LazySegTree s f a Source #
A lazily propagated segment tree defined around SegAct.
Since: 1.0.0.0
Constructors
new :: (HasCallStack, PrimMonad m, Monoid f, Unbox f, Monoid a, Unbox a) => Int -> m (LazySegTree (PrimState m) f a) Source #
Creates an array of length \(n\). All the elements are initialized to mempty.
Constraints
- \(0 \leq n\)
Complexity
- \(O(n)\)
Since: 1.0.0.0
build :: (PrimMonad m, Monoid f, Unbox f, Monoid a, Unbox a) => Vector a -> m (LazySegTree (PrimState m) f a) Source #
Creates an array with initial values \(vs\).
Constraints
- \(0 \leq n\)
Complexity
- \(O(n)\)
Since: 1.0.0.0
Accessing elements
write :: (HasCallStack, PrimMonad m, SegAct f a, Unbox f, Monoid a, Unbox a) => LazySegTree (PrimState m) f a -> Int -> a -> m () Source #
Sets \(p\)-th value of the array to \(x\).
Constraints
- \(0 \leq p \lt n\)
Complexity
- \(O(\log n)\)
Since: 1.0.0.0
modify :: (HasCallStack, PrimMonad m, SegAct f a, Unbox f, Monoid a, Unbox a) => LazySegTree (PrimState m) f a -> (a -> a) -> Int -> m () Source #
(Extra API) Modifies \(p\)-th value with a function \(f\).
Constraints
- \(0 \leq p \lt n\)
Complexity
- \(O(\log n)\)
Since: 1.0.0.0
modifyM :: (HasCallStack, PrimMonad m, SegAct f a, Unbox f, Monoid a, Unbox a) => LazySegTree (PrimState m) f a -> (a -> m a) -> Int -> m () Source #
(Extra API) Modifies \(p\)-th value with a monadic function \(f\).
Constraints
- \(0 \leq p \lt n\)
Complexity
- \(O(\log n)\)
Since: 1.0.0.0
exchange :: (HasCallStack, PrimMonad m, SegAct f a, Unbox f, Monoid a, Unbox a) => LazySegTree (PrimState m) f a -> Int -> a -> m a Source #
(Extra API) Sets \(p\)-th value of the array to \(x\) and returns the old value.
Constraints
- \(0 \leq p \lt n\)
Complexity
- \(O(\log n)\)
Since: 1.1.0.0
read :: (HasCallStack, PrimMonad m, SegAct f a, Unbox f, Monoid a, Unbox a) => LazySegTree (PrimState m) f a -> Int -> m a Source #
Returns \(p\)-th value of the array.
Constraints
- \(0 \leq p \lt n\)
Complexity
- \(O(\log n)\)
Since: 1.0.0.0
Products
prod :: (HasCallStack, PrimMonad m, SegAct f a, Unbox f, Monoid a, Unbox a) => LazySegTree (PrimState m) f a -> Int -> Int -> m a Source #
Returns the product of \([a[l], ..., a[r - 1]]\), assuming the properties of the monoid. It
returns mempty if \(l = r\).
Constraints
- \(0 \leq l \leq r \leq n\)
Complexity
- \(O(\log n)\)
Since: 1.0.0.0
prodMaybe :: (HasCallStack, PrimMonad m, SegAct f a, Unbox f, Monoid a, Unbox a) => LazySegTree (PrimState m) f a -> Int -> Int -> m (Maybe a) Source #
allProd :: (PrimMonad m, Monoid a, Unbox a) => LazySegTree (PrimState m) f a -> m a Source #
Returns the product of \([op(a[0], ..., a[n - 1])]\), assuming the properties of the monoid. It
returns mempty if \(n = 0\).
Complexity
- \(O(1)\)
Since: 1.0.0.0
Applications
applyAt :: (HasCallStack, PrimMonad m, SegAct f a, Unbox f, Monoid a, Unbox a) => LazySegTree (PrimState m) f a -> Int -> f -> m () Source #
Applies segAct f to an index \(p\).
Constraints
- \(0 \leq p \lt n\)
Complexity
- \(O(\log n)\)
Since: 1.0.0.0
applyIn :: (HasCallStack, PrimMonad m, SegAct f a, Unbox f, Monoid a, Unbox a) => LazySegTree (PrimState m) f a -> Int -> Int -> f -> m () Source #
Applies segAct f to an interval \([l, r)\).
Constraints
- \(0 \leq l \leq r \leq n\)
Complexity
- \(O(\log n)\)
Since: 1.0.0.0
Binary searches
Left binary searches
minLeft :: (HasCallStack, PrimMonad m, SegAct f a, Unbox f, Monoid a, Unbox a) => LazySegTree (PrimState m) f a -> Int -> (a -> Bool) -> m Int Source #
Applies a binary search on the segment tree. It returns an index \(l\) that satisfies both of the following.
- \(l = r\) or \(g(a[l] \cdot a[l + 1] \cdot ... \cdot a[r - 1])\) returns
True. - \(l = 0\) or \(g(a[l - 1] \cdot a[l] \cdot ... \cdot a[r - 1])\) returns
False.
If \(g\) is monotone, this is the minimum \(l\) that satisfies \(g(a[l] \cdot a[l + 1] \cdot ... \cdot a[r - 1])\).
Constraints
- if \(g\) is called with the same argument, it returns the same value, i.e., \(g\) has no side effect.
g mempty == True.- \(0 \leq r \leq n\)
Complexity
- \(O(\log n)\)
Since: 1.0.0.0
minLeftM :: (HasCallStack, PrimMonad m, SegAct f a, Unbox f, Monoid a, Unbox a) => LazySegTree (PrimState m) f a -> Int -> (a -> m Bool) -> m Int Source #
Monadic variant of minLeft.
Constraints
- if \(g\) is called with the same argument, it returns the same value, i.e., \(g\) has no side effect.
g mempty == True.- \(0 \leq r \leq n\)
Complexity
- \(O(\log n)\)
Since: 1.0.0.0
Right binary searches
maxRight :: (HasCallStack, PrimMonad m, SegAct f a, Unbox f, Monoid a, Unbox a) => LazySegTree (PrimState m) f a -> Int -> (a -> Bool) -> m Int Source #
Applies a binary search on the segment tree. It returns an index \(r\) that satisfies both of the followings.
- \(r = l\) or \(g(a[l] \cdot a[l + 1] \cdot ... \cdot a[r - 1]))\) returns
True. - \(r = n\) or \(g(a[l] \cdot a[l + 1] \cdot ... \cdot a[r]))\) returns
False.
If \(g\) is monotone, this is the maximum \(r\) that satisfies \(g(a[l] \cdot a[l + 1] \cdot ... \cdot a[r - 1])\).
Constraints
- If \(g\) is called with the same argument, it returns the same value, i.e., \(g\) has no side effect.
g mempty == True.- \(0 \leq l \leq n\)
Complexity
- \(O(\log n)\)
Since: 1.0.0.0
maxRightM :: (HasCallStack, PrimMonad m, SegAct f a, Unbox f, Monoid a, Unbox a) => LazySegTree (PrimState m) f a -> Int -> (a -> m Bool) -> m Int Source #
Monadic variant of maxRight.
Constraints
- If \(g\) is called with the same argument, it returns the same value, i.e., \(g\) has no side effect.
g mempty == True.- \(0 \leq l \leq n\)
Complexity
- \(O(\log n)\)
Since: 1.0.0.0
Conversions
freeze :: (PrimMonad m, SegAct f a, Unbox f, Monoid a, Unbox a) => LazySegTree (PrimState m) f a -> m (Vector a) Source #
\(O(n)\) Yields an immutable copy of the mutable vector.
Since: 1.0.0.0
unsafeFreeze :: (PrimMonad m, SegAct f a, Unbox f, Monoid a, Unbox a) => LazySegTree (PrimState m) f a -> m (Vector a) Source #
\(O(n)\) Unsafely converts a mutable vector to an immutable one without copying. The mutable vector may not be used after this operation.
Since: 1.0.0.0