AtCoder.LazySegTree

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

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:

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

>>> 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 Data.Vector.Unboxed.DoNotUnboxStrict or the like.

Major changes from the original ac-library

• The API is based on Monoid and SegAct, not the functions op, e, mapping, composition and id.
• get and set are renamed to read and write.
• modify, modifyM, exchange, freeze and unsafeFreeze are added.

Since: 1.0.0.0

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

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

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

Lazy segment tree action \(f(x)\).

Since: 1.0.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.0

Instances

Monoid a => SegAct (RangeSet a) a

Since: 1.0.0.0

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

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

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 (Mat2x2 a) (V2 a)

Since: 1.1.0.0

Defined in AtCoder.Extra.Monoid.Mat2x2

Methods

segAct :: Mat2x2 a -> V2 a -> V2 a

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

Monoid (Max a) => SegAct (RangeAdd (Max a)) (Max a)

Since: 1.1.0.0

Defined in AtCoder.Extra.Monoid.RangeAdd

Methods

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

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

Monoid (Min a) => SegAct (RangeAdd (Min a)) (Min a)

Since: 1.1.0.0

Defined in AtCoder.Extra.Monoid.RangeAdd

Methods

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

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

Monoid (Sum a) => SegAct (RangeAdd (Sum a)) (Sum a)

Since: 1.1.0.0

Defined in AtCoder.Extra.Monoid.RangeAdd

Methods

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

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

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

Since: 1.0.0.0

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

Defined in AtCoder.Extra.Monoid.Affine1

Methods

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

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

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

Since: 1.1.0.0

Defined in AtCoder.Extra.Monoid.Mat2x2

Methods

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

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

data LazySegTree s f a

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)

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)

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

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

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

(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

(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

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

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)

Total variant of prod. Returns the product of \([a[l], ..., a[r - 1]]\), assuming the properties of the monoid. Returns Just mempty if \(l = r\). It returns Nothing if the interval is invalid.

Complexity

• \(O(\log n)\)

Since: 1.0.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.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.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.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.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 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

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

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)

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

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