| Safe Haskell | None |
|---|---|
| Language | GHC2021 |
AtCoder.Extra.LazyKdTree
Description
Static, \(k\)-dimensional tree \((k = 2)\) with lazily propagated monoid actions and commutative acted monoids.
- Point coordinates are fixed on
buildand cannot be moved or added later. - Multiple points can exist at the same coordinate.
Examples
>>>import AtCoder.Extra.LazyKdTree qualified as LKT>>>import AtCoder.Extra.Monoid.Affine1 (Affine1)>>>import AtCoder.Extra.Monoid.Affine1 qualified as Affine1>>>import Data.Semigroup (Sum (..))>>>import Data.Vector.Unboxed qualified as VU>>>let xyws = VU.fromList [(0, 0, Sum 1), (1, 1, Sum 2), (4, 2, Sum 3)]>>>lkt <- LKT.build3 @_ @(Affine1 Int) @(Sum Int) xyws
>>>-- Get monoid product in [0, 2) x [0, 2)>>>LKT.prod lkt 0 2 0 2Sum {getSum = 3}
>>>LKT.applyIn lkt 0 2 0 2 $ Affine1.new 2 1>>>LKT.prod lkt 0 2 0 2Sum {getSum = 8}
>>>LKT.write lkt 0 $ Sum 10>>>LKT.prod lkt 0 2 0 2Sum {getSum = 15}
Since: 1.2.2.0
Synopsis
- data LazyKdTree s f a = LazyKdTree {}
- class Monoid f => SegAct f a where
- segAct :: f -> a -> a
- segActWithLength :: Int -> f -> a -> a
- new :: (HasCallStack, PrimMonad m, Monoid f, Unbox f, Monoid a, Unbox a) => Vector Int -> Vector Int -> m (LazyKdTree (PrimState m) f a)
- build :: (HasCallStack, PrimMonad m, Monoid f, Unbox f, Semigroup a, Unbox a) => Vector Int -> Vector Int -> Vector a -> m (LazyKdTree (PrimState m) f a)
- build2 :: (HasCallStack, PrimMonad m, Monoid f, Unbox f, Semigroup a, Unbox a) => Vector (Int, Int) -> Vector a -> m (LazyKdTree (PrimState m) f a)
- build3 :: (HasCallStack, PrimMonad m, Monoid f, Unbox f, Semigroup a, Unbox a) => Vector (Int, Int, a) -> m (LazyKdTree (PrimState m) f a)
- write :: (HasCallStack, PrimMonad m, SegAct f a, Eq f, Unbox f, Semigroup a, Unbox a) => LazyKdTree (PrimState m) f a -> Int -> a -> m ()
- modify :: (HasCallStack, PrimMonad m, SegAct f a, Eq f, Unbox f, Semigroup a, Unbox a) => LazyKdTree (PrimState m) f a -> (a -> a) -> Int -> m ()
- modifyM :: (HasCallStack, PrimMonad m, SegAct f a, Eq f, Unbox f, Semigroup a, Unbox a) => LazyKdTree (PrimState m) f a -> (a -> m a) -> Int -> m ()
- prod :: (HasCallStack, PrimMonad m, Eq f, SegAct f a, Eq f, Unbox f, Monoid a, Unbox a) => LazyKdTree (PrimState m) f a -> Int -> Int -> Int -> Int -> m a
- allProd :: (PrimMonad m, Monoid a, Unbox a) => LazyKdTree (PrimState m) f a -> m a
- applyIn :: (HasCallStack, PrimMonad m, Eq f, SegAct f a, Unbox f, Monoid a, Unbox a) => LazyKdTree (PrimState m) f a -> Int -> Int -> Int -> Int -> f -> m ()
K-dimensional tree
data LazyKdTree s f a Source #
Static, \(k\)-dimensional tree \((k = 2)\) with lazily propagated monoid actions and commutative monoids.
Since: 1.2.2.0
Constructors
| LazyKdTree | |
Fields
| |
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 =segActf2 (segActf1 x)- Identity map
segActmemptyx = x- Endomorphism
segActf (x1<>x2) = (segActf x1)<>(segActf x2)
If you implement SegAct via segActWithLength, satisfy one more propety:
- Linear left monoid action
.segActWithLengthlen f (stimes len a) =stimeslen (segActf a)
Invariant
In SegAct instances, new semigroup values are always given from the left: new . The
order is important for non-commutative monoid implementations.<> 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 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 (Affine1a) = MV_Affine1 (VU.MVector s (Affine1a)) newtype instance VU.Vector (Affine1a) = V_Affine1 (VU.Vector (Affine1a)) deriving instance (VU.Unbox a) => VGM.MVector VUM.MVector (Affine1a) deriving instance (VU.Unbox a) => VG.Vector VU.Vector (Affine1a) instance (VU.Unbox a) => VU.Unbox (Affine1a)
Example contest template
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!"
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
| SegAct () a Source # | Since: 1.2.0.0 |
Defined in AtCoder.LazySegTree | |
| Monoid a => SegAct (RangeSet a) a Source # | Since: 1.0.0.0 |
Defined in AtCoder.Extra.Monoid.RangeSet | |
| Num a => SegAct (Affine1 (Sum a)) (Sum a) Source # | Since: 1.0.0.0 |
| Num a => SegAct (Affine1 a) (V2 a) Source # | Since: 1.2.2.0 |
| Num a => SegAct (Affine1 a) (Sum a) Source # | Since: 1.0.0.0 |
| Num a => SegAct (Mat2x2 a) (V2 a) Source # | Since: 1.1.0.0 |
| (Num a, Monoid (Max a)) => SegAct (RangeAdd (Max a)) (Max a) Source # | Since: 1.1.0.0 |
| (Num a, Monoid (Min a)) => SegAct (RangeAdd (Min a)) (Min a) Source # | Since: 1.1.0.0 |
| Num a => SegAct (RangeAdd (Sum a)) (Sum a) Source # | Since: 1.2.0.0 |
| Num a => SegAct (Dual (Affine1 (Sum a))) (Sum a) Source # | Since: 1.0.0.0 |
| Num a => SegAct (Dual (Affine1 a)) (V2 a) Source # | Since: 1.2.2.0 |
| Num a => SegAct (Dual (Affine1 a)) (Sum a) Source # | Since: 1.0.0.0 |
| Num a => SegAct (Dual (Mat2x2 a)) (V2 a) Source # | Since: 1.1.0.0 |
Constructors
Arguments
| :: (HasCallStack, PrimMonad m, Monoid f, Unbox f, Monoid a, Unbox a) | |
| => Vector Int | \(x\) coordnates. |
| -> Vector Int | \(y\) coordnates. |
| -> m (LazyKdTree (PrimState m) f a) |
\(O(n \log n)\) Creates a LazyKdTree from xs and ys.
Constraints
- \(|\mathrm{xs}| = |\mathrm{ys}|\)
Since: 1.2.3.0
Arguments
| :: (HasCallStack, PrimMonad m, Monoid f, Unbox f, Semigroup a, Unbox a) | |
| => Vector Int | \(x\) coordnates. |
| -> Vector Int | \(y\) coordnates. |
| -> Vector a | monoid \(v\)alues. |
| -> m (LazyKdTree (PrimState m) f a) |
\(O(n \log n)\) Creates a LazyKdTree from xs, ys and ws vectors.
Constraints
- \(|\mathrm{xs}| = |\mathrm{ys}| = |\mathrm{vs}|\).
Since: 1.2.2.0
Arguments
| :: (HasCallStack, PrimMonad m, Monoid f, Unbox f, Semigroup a, Unbox a) | |
| => Vector (Int, Int) | \((x, y)\) coordinates. |
| -> Vector a | Monoid \(v\)alues. |
| -> m (LazyKdTree (PrimState m) f a) |
\(O(n \log n)\) Creates a LazyKdTree from xys and ws vectors.
Constraints
- \(|\mathrm{xys}| = |\mathrm{vs}|\).
Since: 1.2.2.0
Arguments
| :: (HasCallStack, PrimMonad m, Monoid f, Unbox f, Semigroup a, Unbox a) | |
| => Vector (Int, Int, a) | \((x, y, v)\) tuples. |
| -> m (LazyKdTree (PrimState m) f a) |
\(O(n \log n)\) Creates a LazyKdTree from a xyws vector.
Since: 1.2.2.0
Write
Arguments
| :: (HasCallStack, PrimMonad m, SegAct f a, Eq f, Unbox f, Semigroup a, Unbox a) | |
| => LazyKdTree (PrimState m) f a | |
| -> Int | Original vertex index. |
| -> a | Monoid value. |
| -> m () | Monadic tuple. |
\(O(\log n)\) Writes to the \(k\)-th point's monoid value.
Since: 1.2.2.0
Arguments
| :: (HasCallStack, PrimMonad m, SegAct f a, Eq f, Unbox f, Semigroup a, Unbox a) | |
| => LazyKdTree (PrimState m) f a | |
| -> (a -> a) | \(f\): Creates a new monoid value from the old one. |
| -> Int | \(k\): Original vertex index. |
| -> m () | Monadic tuple. |
\(O(\log n)\) Given a user function \(f\), modifies the \(k\)-th point's monoid value with it.
Since: 1.2.2.0
Arguments
| :: (HasCallStack, PrimMonad m, SegAct f a, Eq f, Unbox f, Semigroup a, Unbox a) | |
| => LazyKdTree (PrimState m) f a | |
| -> (a -> m a) | \(f\): Creates a new monoid value from the old one. |
| -> Int | \(k\): Original vertex index. |
| -> m () | Monadic tuple. |
\(O(\log n)\) Given a user function \(f\), modifies the \(k\)-th point's monoid value with it.
Since: 1.2.2.0
Monoid products
Arguments
| :: (HasCallStack, PrimMonad m, Eq f, SegAct f a, Eq f, Unbox f, Monoid a, Unbox a) | |
| => LazyKdTree (PrimState m) f a | |
| -> Int | \(x_1\) |
| -> Int | \(x_2\) |
| -> Int | \(y_1\) |
| -> Int | \(y_2\) |
| -> m a | \(\Pi_{p \in [x_1, x_2) \times [y_1, y_2)} a_p\) |
\(O(\sqrt n)\) Returns monoid product \(\Pi_{p \in [x_1, x_2) \times [y_1, y_2)} a_p\).
Since: 1.2.2.0
Arguments
| :: (PrimMonad m, Monoid a, Unbox a) | |
| => LazyKdTree (PrimState m) f a | |
| -> m a | \(\Pi_{p \in [-\infty, \infty) \times [-\infty, \infty)} a_p\) |
\(O(1)\) Returns monoid product \(\Pi_{p \in [-\infty, \infty) \times [-\infty, \infty)} a_p\).
Since: 1.2.2.0
Apply
Arguments
| :: (HasCallStack, PrimMonad m, Eq f, SegAct f a, Unbox f, Monoid a, Unbox a) | |
| => LazyKdTree (PrimState m) f a | |
| -> Int | \(x_1\) |
| -> Int | \(x_2\) |
| -> Int | \(y_1\) |
| -> Int | \(y_2\) |
| -> f | \(f\) |
| -> m () | Monadic tuple. |
\(O(\log n)\) Given a rectangle \([x_1, x_2) \times [y_1, y_2)\), applies a monoid action to it.
Since: 1.2.2.0