Safe Haskell | None |
---|---|
Language | GHC2021 |
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 1
Sum {getSum = 5}>>>
LST.prod seg 0 3 -- product (fold) of `Sum Int` in interval [0, 3)
Sum {getSum = 14}>>>
LST.allProd seg
Sum {getSum = 24}
Run binary search in \(O(\log n\) time complexity:
>>>
LST.maxRight seg 0 (<= (Sum 10)) -- sum [0, 2) = 7 <= 10
2>>>
LST.minLeft seg 4 (<= (Sum 10)) -- sum [3, 4) = 10 <= 10
3
Inspect all the values in \(O(n \log n)\) with freeze
or unsafeFreeze
. Note that they
propagete all the applied actions:
>>>
VU.map getSum <$> LST.freeze seg
[2,5,7,10]
Tips
prod
returns \(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 inDoNotUnboxStrict
or the like.
Major changes from the original ac-library
- The API is based on
Monoid
andSegAct
, not the functionsop
,e
,mapping
,composition
andid
. - The functions names follow the vector package:
get
andset
are renamed toread
andwrite
.modify
,modifyM
,freeze
andunsafeFreeze
are added.
Since: 1.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 ()
- 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
- 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 #
Typeclass reprentation of the LazySegTree
properties. User can implement either segAct
or
segActWithLength
.
Instances should satisfy the follwing:
- 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 segActWithLength
, satisfy one more propety:
- Linear left monoid action
.segActWithLength
len f a =stimes
len (segAct
f a) a
Note that in SegAct
instances, new semigroup values are always given from the left: new
.<>
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
Nothing
Lazy segment tree action \(f(x)\).
Since: 1.0.0
segActWithLength :: Int -> f -> a -> a #
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
Instances
data LazySegTree s f a #
Lazy segment tree defined around SegAct
.
Since: 1.0.0
Constructors
new :: (HasCallStack, PrimMonad m, Monoid f, Unbox f, Monoid a, Unbox a) => Int -> m (LazySegTree (PrimState m) f a) #
Creates an array of length n
. All the elements are initialized to mempty
.
Constraints
- \(0 \leq n\)
Complexity
- \(O(n)\)
Since: 1.0.0
build :: (PrimMonad m, Monoid f, Unbox f, Monoid a, Unbox a) => Vector a -> m (LazySegTree (PrimState m) f a) #
Creates an array with initial values vs
.
Constraints
- \(0 \leq n\)
Complexity
- \(O(n)\)
Since: 1.0.0
Accessing individual elements
write :: (HasCallStack, PrimMonad m, SegAct f a, Unbox f, Monoid a, Unbox a) => LazySegTree (PrimState m) f a -> Int -> a -> m () #
Sets \(p\)-th value of the array to \(x\).
Constraints
- \(0 \leq p \lt n\)
Complexity
- \(O(\log n)\)
Since: 1.0.0
modify :: (HasCallStack, PrimMonad m, SegAct f a, Unbox f, Monoid a, Unbox a) => LazySegTree (PrimState m) f a -> (a -> a) -> Int -> m () #
(Extra API) Modifies \(p\)-th value of the array to \(x\).
Constraints
- \(0 \leq p \lt n\)
Complexity
- \(O(\log n)\)
Since: 1.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 () #
(Extra API) Modifies \(p\)-th value of the array to \(x\).
Constraints
- \(0 \leq p \lt n\)
Complexity
- \(O(\log n)\)
Since: 1.0.0
read :: (HasCallStack, PrimMonad m, SegAct f a, Unbox f, Monoid a, Unbox a) => LazySegTree (PrimState m) f a -> Int -> m a #
Returns \(p\)-th value of the array.
Constraints
- \(0 \leq p \lt n\)
Complexity
- \(O(\log n)\)
Since: 1.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 #
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
allProd :: (PrimMonad m, Monoid a, Unbox a) => LazySegTree (PrimState m) f a -> m a #
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
Applications
applyAt :: (HasCallStack, PrimMonad m, SegAct f a, Unbox f, Monoid a, Unbox a) => LazySegTree (PrimState m) f a -> Int -> f -> m () #
Applies segAct f
to an index p
.
Constraints
- \(0 \leq p \lt n\)
Complexity
- \(O(\log n)\)
Since: 1.0.0
applyIn :: (HasCallStack, PrimMonad m, SegAct f a, Unbox f, Monoid a, Unbox a) => LazySegTree (PrimState m) f a -> Int -> Int -> f -> m () #
Applies segAct f
to an interval [l, r)
.
Constraints
- \(0 \leq l \leq r \leq n\)
Complexity
- \(O(\log n)\)
Since: 1.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 #
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
minLeftM :: (HasCallStack, PrimMonad m, SegAct f a, Unbox f, Monoid a, Unbox a) => LazySegTree (PrimState m) f a -> Int -> (a -> m Bool) -> m Int #
Monadic version 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
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 #
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
maxRightM :: (HasCallStack, PrimMonad m, SegAct f a, Unbox f, Monoid a, Unbox a) => LazySegTree (PrimState m) f a -> Int -> (a -> m Bool) -> m Int #
Monadic version 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
Conversions
freeze :: (PrimMonad m, SegAct f a, Unbox f, Monoid a, Unbox a) => LazySegTree (PrimState m) f a -> m (Vector a) #
\(O(n)\) Yields an immutable copy of the mutable vector.
Since: 1.0.0
unsafeFreeze :: (PrimMonad m, SegAct f a, Unbox f, Monoid a, Unbox a) => LazySegTree (PrimState m) f a -> m (Vector a) #
\(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