Re-exports

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)

Define your monoid action F and your acted monoid X:

{-# LANGUAGE DerivingStrategies #-}
{-# 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!"

>>> import AtCoder.Extra.Monoid (SegAct(..), Affine1(..))
>>> import AtCoder.LazySegTree qualified as LST
>>> seg <- LST.build @_ @(Affine1 Int) @(Sum Int) $ VU.generate 3 Sum -- [0, 1, 2]
>>> LST.applyIn seg 0 3 $ Affine1 (2, 1) -- [1, 3, 5]
>>> getSum <$> LST.allProd seg
9

>>> import AtCoder.Extra.Monoid.Mat2x2 qualified as Mat2x2
>>> import AtCoder.Extra.Monoid.V2 qualified as V2
>>> import AtCoder.Extra.Monoid (SegAct(..), Mat2x2(..), V2(..))
>>> import AtCoder.LazySegTree qualified as LST
>>> seg <- LST.build @_ @(Mat2x2 Int) @(V2 Int) $ VU.generate 3 V2.new -- [0, 1, 2]
>>> LST.applyIn seg 0 3 $ Mat2x2.new 2 1 -- [1, 3, 5]
>>> V2.unV2 <$> LST.allProd seg
9

>>> import AtCoder.Extra.Monoid.Mat2x2 (Mat2x2(..))
>>> import AtCoder.Extra.Monoid.Mat2x2 qualified as Mat2x2
>>> import AtCoder.Extra.Monoid.V2 (V2(..))
>>> import AtCoder.Extra.Monoid.V2 qualified as V2
>>> import AtCoder.LazySegTree qualified as LST
>>> import Data.Vector.Unboxed qualified as VU
>>> seg <- LST.build @_ @(Mat2x2 Int) @(V2 Int) . VU.map V2.new $ VU.fromList [1, 2, 3, 4]
>>> LST.applyIn seg 1 3 $ Mat2x2.new 2 1 -- [1, 5, 7, 4]
>>> V2.unV2 <$> LST.prod seg 1 3
12

>>> import AtCoder.Extra.Monoid (SegAct(..), RangeAdd(..))
>>> import AtCoder.LazySegTree qualified as LST
>>> import Data.Semigroup (Sum(..))
>>> seg <- LST.build @_ @(RangeAdd (Sum Int)) @(Sum Int) $ VU.generate 3 Sum -- [0, 1, 2]
>>> LST.applyIn seg 0 3 $ RangeAdd (Sum 5) -- [5, 6, 7]
>>> getSum <$> LST.prod seg 0 3
18

>>> import AtCoder.Extra.Monoid (SegAct(..), RangeAdd(..))
>>> import AtCoder.LazySegTree qualified as LST
>>> import Data.Semigroup (Max(..))
>>> seg <- LST.build @_ @(RangeAdd (Max Int)) @(Max Int) $ VU.generate 3 Max -- [0, 1, 2]
>>> LST.applyIn seg 0 3 $ RangeAdd (Max 5) -- [5, 6, 7]
>>> getMax <$> LST.prod seg 0 3
7

>>> import AtCoder.Extra.Monoid (SegAct(..), RangeSet(..))
>>> import AtCoder.LazySegTree qualified as LST
>>> import Data.Bit (Bit (..))
>>> import Data.Semigroup (Product(..))
>>> seg <- LST.build @_ @(RangeSet (Product Int)) @(Product Int) $ VU.generate 4 Product -- [0, 1, 2, 3]
>>> LST.applyIn seg 0 3 $ RangeSet (Bit True, Product 5) -- [5, 5, 5, 3]
>>> getProduct <$> LST.prod seg 0 4
375

It's convenient to define a type alias of RollingHash:

>>> import AtCoder.Extra.Monoid.RollingHash qualified as RH
>>> import AtCoder.SegTree qualified as ST
>>> import Data.Char (ord)
>>> import Data.Semigroup (Dual (..))
>>> type RH = RH.RollingHash 100 2305843009213693951

Let's test whether "abcba" is a palindrome:

>>> seg <- ST.build @_ @RH . VU.map (RH.unsafeNew . ord) $ VU.fromList "abcba"
>>> seg' <- ST.build @_ @(Dual RH) . VU.map (Dual . RH.unsafeNew . ord) $ VU.fromList "abcba"
>>> hash1 <- ST.prod seg 2 5       --   cba  (left to right)
>>> Dual hash2 <- ST.prod seg' 0 3 -- abc    (right to lett)
>>> hash1 == hash2
True