ac-library-hs-1.2.1.0: Data structures and algorithms
Safe HaskellSafe-Inferred
LanguageGHC2021

AtCoder.Extra.DynLazySegTree.Raw

Description

Base module of a dynamic, lazily propagated segment tree.

Since: 1.2.1.0

Synopsis

Dynamic, lazily propagated segment tree

data DynLazySegTree s f a Source #

A dynamic, lazily propagated segment tree that covers a half-open interval \([l_0, r_0)\). The nodes are instantinated as needed.

Since: 1.2.1.0

Constructors

DynLazySegTree 

Fields

  • capacityLdst :: !Int

    The maximum number of nodes allocated

    Since: 1.2.1.0

  • isPersistentLdst :: !Bool

    Whether the data is persistent or not

    Since: 1.2.1.0

  • l0Ldst :: !Int

    Left index boundary (inclusive)

    Since: 1.2.1.0

  • r0Ldst :: !Int

    Right index boundary (exclusive)

    Since: 1.2.1.0

  • initialProdLdst :: !(Int -> Int -> a)

    Initial monoid value assignment \(g: (l, r) \rightarrow a\)

    Since: 1.2.1.0

  • poolLdst :: !(Pool s ())

    Pool for free slot management.

    Since: 1.2.1.0

  • lLdst :: !(MVector s Index)

    Decomposed node storage: left children

    Since: 1.2.1.0

  • rLdst :: !(MVector s Index)

    Decomposed node storage: right children

    Since: 1.2.1.0

  • xLdst :: !(MVector s a)

    Decomposed node storage: monoid value

    Since: 1.2.1.0

  • lazyLdst :: !(MVector s f)

    Decomposed node storage: lazily propagated monoid action

    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 <> old. The order is important for non-commutative monoid implementations.

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

Instances details
SegAct () a Source #

Since: 1.2.0.0

Instance details

Defined in AtCoder.LazySegTree

Methods

segAct :: () -> a -> a Source #

segActWithLength :: Int -> () -> a -> a Source #

Monoid a => SegAct (RangeSet a) a Source #

Since: 1.0.0.0

Instance details

Defined in AtCoder.Extra.Monoid.RangeSet

Methods

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

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

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

Since: 1.0.0.0

Instance details

Defined in AtCoder.Extra.Monoid.Affine1

Methods

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

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

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

Since: 1.0.0.0

Instance details

Defined in AtCoder.Extra.Monoid.Affine1

Methods

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

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

Num a => SegAct (Mat2x2 a) (V2 a) Source #

Since: 1.1.0.0

Instance details

Defined in AtCoder.Extra.Monoid.Mat2x2

Methods

segAct :: Mat2x2 a -> V2 a -> V2 a Source #

segActWithLength :: Int -> Mat2x2 a -> V2 a -> V2 a Source #

(Num a, Monoid (Max a)) => SegAct (RangeAdd (Max a)) (Max a) Source #

Since: 1.1.0.0

Instance details

Defined in AtCoder.Extra.Monoid.RangeAdd

Methods

segAct :: RangeAdd (Max a) -> Max a -> Max a Source #

segActWithLength :: Int -> RangeAdd (Max a) -> Max a -> Max a Source #

(Num a, Monoid (Min a)) => SegAct (RangeAdd (Min a)) (Min a) Source #

Since: 1.1.0.0

Instance details

Defined in AtCoder.Extra.Monoid.RangeAdd

Methods

segAct :: RangeAdd (Min a) -> Min a -> Min a Source #

segActWithLength :: Int -> RangeAdd (Min a) -> Min a -> Min a Source #

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

Since: 1.2.0.0

Instance details

Defined in AtCoder.Extra.Monoid.RangeAdd

Methods

segAct :: RangeAdd (Sum a) -> Sum a -> Sum a Source #

segActWithLength :: Int -> RangeAdd (Sum a) -> Sum a -> Sum a Source #

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

Since: 1.0.0.0

Instance details

Defined in AtCoder.Extra.Monoid.Affine1

Methods

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

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

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

Since: 1.0.0.0

Instance details

Defined in AtCoder.Extra.Monoid.Affine1

Methods

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

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

Num a => SegAct (Dual (Mat2x2 a)) (V2 a) Source #

Since: 1.1.0.0

Instance details

Defined in AtCoder.Extra.Monoid.Mat2x2

Methods

segAct :: Dual (Mat2x2 a) -> V2 a -> V2 a Source #

segActWithLength :: Int -> Dual (Mat2x2 a) -> V2 a -> V2 a Source #

newtype Index Source #

Strongly typed index of pool items. User has to explicitly corece on raw index use.

Constructors

Index 

Fields

Instances

Instances details
Show Index Source # 
Instance details

Defined in AtCoder.Extra.Pool

Methods

showsPrec :: Int -> Index -> ShowS #

show :: Index -> String #

showList :: [Index] -> ShowS #

Eq Index Source # 
Instance details

Defined in AtCoder.Extra.Pool

Methods

(==) :: Index -> Index -> Bool #

(/=) :: Index -> Index -> Bool #

Ord Index Source # 
Instance details

Defined in AtCoder.Extra.Pool

Methods

compare :: Index -> Index -> Ordering #

(<) :: Index -> Index -> Bool #

(<=) :: Index -> Index -> Bool #

(>) :: Index -> Index -> Bool #

(>=) :: Index -> Index -> Bool #

max :: Index -> Index -> Index #

min :: Index -> Index -> Index #

Prim Index Source # 
Instance details

Defined in AtCoder.Extra.Pool

Unbox Index Source # 
Instance details

Defined in AtCoder.Extra.Pool

Vector Vector Index Source # 
Instance details

Defined in AtCoder.Extra.Pool

MVector MVector Index Source # 
Instance details

Defined in AtCoder.Extra.Pool

newtype Vector Index Source # 
Instance details

Defined in AtCoder.Extra.Pool

newtype Vector Index = V_Index (Vector Index)
newtype MVector s Index Source # 
Instance details

Defined in AtCoder.Extra.Pool

newtype MVector s Index = MV_Index (MVector s Index)

Constructors

newST :: (HasCallStack, Unbox f, Unbox a) => Bool -> Int -> Int -> Int -> (Int -> Int -> a) -> ST s (DynLazySegTree s f a) Source #

\(O(n)\)

Since: 1.2.1.0

newRootST :: (HasCallStack, Monoid f, Unbox f, Monoid a, Unbox a) => DynLazySegTree s f a -> ST s Index Source #

\(O(1)\)

Since: 1.2.1.0

newNodeST :: (HasCallStack, Monoid f, Unbox f, Monoid a, Unbox a) => DynLazySegTree s f a -> a -> ST s Index Source #

\(O(1)\)

Since: 1.2.1.0

newSeqST :: (HasCallStack, Monoid f, Unbox f, Monoid a, Unbox a) => DynLazySegTree s f a -> Vector a -> ST s Index Source #

\(O(L)\)

Since: 1.2.1.0

Accessing elements

modifyMST :: forall m f a. (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 Index Source #

\(O(\log L)\)

Since: 1.2.1.0

Products

prodST :: forall f a s. (HasCallStack, SegAct f a, Monoid f, Unbox f, Monoid a, Unbox a) => DynLazySegTree s f a -> Index -> Int -> Int -> ST s a Source #

\(O(\log L)\)

Since: 1.2.1.0

Applications

applyInST :: forall f a s. (HasCallStack, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a) => DynLazySegTree s f a -> Index -> Int -> Int -> f -> ST s Index Source #

\(O(\log L)\)

Since: 1.2.1.0

Tree operations

copyIntervalWithST Source #

Arguments

:: forall f a s. (HasCallStack, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a) 
=> DynLazySegTree s f a

Dynamic segment tree

-> Index

Root to be modified

-> Index

Another segment tree

-> Int

\(l\)

-> Int

\(r\)

-> f

Action \(f\)

-> ST s Index

New root

\(O(\log L)\)

Since: 1.2.1.0

resetIntervalST :: forall f a s. (HasCallStack, SegAct f a, Eq f, Monoid f, Unbox f, Monoid a, Unbox a) => DynLazySegTree s f a -> Index -> Int -> Int -> ST s Index Source #

\(O(\log L)\) Resets an interval \([l, r)\) to initial monoid values.

Since: 1.2.1.0

Binary searches

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(\log L)\)

Since: 1.2.1.0