ac-library-hs-0.1.0.0: Data structures and algorithms
Safe HaskellNone
LanguageGHC2021

AtCoder.LazySegTree

Description

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 (segAct f) and \(S\) is a Monoid. 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

Expand

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. build @_ @f @a constructs a LazySegTree 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 in Dual.
  • If you ever need to store boxed types to LazySegTree, wrap it in DoNotUnboxStrict or the like.

Major changes from the original ac-library

Since: 1.0.0

Synopsis

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

Expand

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 (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

Expand

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

Minimal complete definition

Nothing

Methods

segAct :: f -> a -> a #

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

Instances details
Monoid a => SegAct (RangeSet a) a #

Since: 1.0.0

Instance details

Defined in AtCoder.Extra.Monoid.RangeSet

Methods

segAct :: RangeSet a -> a -> a #

segActWithLength :: Int -> RangeSet a -> a -> a #

Num a => SegAct (Affine1 (Sum a)) (Sum a) #

Since: 1.0.0

Instance details

Defined in AtCoder.Extra.Monoid.Affine1

Methods

segAct :: Affine1 (Sum a) -> Sum a -> Sum a #

segActWithLength :: Int -> Affine1 (Sum a) -> Sum a -> Sum a #

Num a => SegAct (Affine1 a) (Sum a) #

Since: 1.0.0

Instance details

Defined in AtCoder.Extra.Monoid.Affine1

Methods

segAct :: Affine1 a -> Sum a -> Sum a #

segActWithLength :: Int -> Affine1 a -> Sum a -> Sum a #

Num a => SegAct (RangeAdd a) (Sum a) #

Since: 1.0.0

Instance details

Defined in AtCoder.Extra.Monoid.RangeAdd

Methods

segAct :: RangeAdd a -> Sum a -> Sum a #

segActWithLength :: Int -> RangeAdd a -> Sum a -> Sum a #

Num a => SegAct (RangeAddId a) (Max a) #

Since: 1.0.0

Instance details

Defined in AtCoder.Extra.Monoid.RangeAddId

Methods

segAct :: RangeAddId a -> Max a -> Max a #

segActWithLength :: Int -> RangeAddId a -> Max a -> Max a #

Num a => SegAct (RangeAddId a) (Min a) #

Since: 1.0.0

Instance details

Defined in AtCoder.Extra.Monoid.RangeAddId

Methods

segAct :: RangeAddId a -> Min a -> Min a #

segActWithLength :: Int -> RangeAddId a -> Min a -> Min a #

(Ord a, Bounded a) => SegAct (RangeSetId (Max a)) (Max a) #

Since: 1.0.0

Instance details

Defined in AtCoder.Extra.Monoid.RangeSetId

Methods

segAct :: RangeSetId (Max a) -> Max a -> Max a #

segActWithLength :: Int -> RangeSetId (Max a) -> Max a -> Max a #

(Ord a, Bounded a) => SegAct (RangeSetId (Min a)) (Min a) #

Since: 1.0.0

Instance details

Defined in AtCoder.Extra.Monoid.RangeSetId

Methods

segAct :: RangeSetId (Min a) -> Min a -> Min a #

segActWithLength :: Int -> RangeSetId (Min a) -> Min a -> Min a #

Num a => SegAct (Dual (Affine1 (Sum a))) (Sum a) #

Since: 1.0.0

Instance details

Defined in AtCoder.Extra.Monoid.Affine1

Methods

segAct :: Dual (Affine1 (Sum a)) -> Sum a -> Sum a #

segActWithLength :: Int -> Dual (Affine1 (Sum a)) -> Sum a -> Sum a #

Num a => SegAct (Dual (Affine1 a)) (Sum a) #

Since: 1.0.0

Instance details

Defined in AtCoder.Extra.Monoid.Affine1

Methods

segAct :: Dual (Affine1 a) -> Sum a -> Sum a #

segActWithLength :: Int -> Dual (Affine1 a) -> Sum a -> Sum a #

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