Safe Haskell	None
Language	GHC2021

AtCoder.Extra.SegTree2d.Dense

Contents

DenseSegTree2d
Constructors
Read
Write
Monoid product

Description

Two-dimensional segment tree for commutative monoids in \([0, w) \times [0, h)\).

Internals

Expand

Take a 2x4 matrix as an example:

5 6 7 8
1 2 3 4

Extend each row as a segment tree:

 - 22 11 15  5  6  7  8
 - 10  3  7  1  2  3  4

Then extend each column as a segment tree:

 -  -  -  -  -  -  -  -
 - 30 14 22  6  8 10 12
 - 26 11 15  5  6  7  8
 - 10  3  7  1  2  3  4

Example

Expand

Create a two-dimensional segment tree for size (w, h) = (4, 2):

>>> import AtCoder.Extra.SegTree2d.Dense qualified as Seg
>>> import Data.Semigroup (Sum (..))
>>> import Data.Vector.Unboxed qualified as VU
>>> seg <- Seg.build @_ @(Sum Int) 4 2 $ VU.fromList [0, 1, 2, 3, 4, 5, 6, 7]

Get monoid product in \([x_1, x_2) \times [y_1, y_2)\) with prod:

>>> Seg.prod seg {- x -} 1 4 {- y -} 0 1
Sum {getSum = 6}

Monoid values can be altered:

>>> Seg.write seg 1 1 20
>>> Seg.prod seg {- x -} 0 2 {- y -} 0 2
Sum {getSum = 25}

>>> Seg.allProd seg
Sum {getSum = 43}

Since: 1.2.3.0

Synopsis

data DenseSegTree2d s a = DenseSegTree2d {
- hDst :: !Int
- wDst :: !Int
- dataDst :: !(MVector s a)
}
new :: (PrimMonad m, Monoid a, Unbox a) => Int -> Int -> m (DenseSegTree2d (PrimState m) a)
build :: (HasCallStack, PrimMonad m, Monoid a, Unbox a) => Int -> Int -> Vector a -> m (DenseSegTree2d (PrimState m) a)
build' :: (HasCallStack, PrimMonad m, Monoid a, Unbox a) => Vector (Vector a) -> m (DenseSegTree2d (PrimState m) a)
read :: (HasCallStack, PrimMonad m, Monoid a, Unbox a) => DenseSegTree2d (PrimState m) a -> Int -> Int -> m a
readMaybe :: (HasCallStack, PrimMonad m, Monoid a, Unbox a) => DenseSegTree2d (PrimState m) a -> Int -> Int -> m (Maybe a)
write :: (HasCallStack, PrimMonad m, Monoid a, Unbox a) => DenseSegTree2d (PrimState m) a -> Int -> Int -> a -> m ()
modify :: (HasCallStack, PrimMonad m, Monoid a, Unbox a) => DenseSegTree2d (PrimState m) a -> (a -> a) -> Int -> Int -> m ()
modifyM :: (HasCallStack, PrimMonad m, Monoid a, Unbox a) => DenseSegTree2d (PrimState m) a -> (a -> m a) -> Int -> Int -> m ()
prod :: (HasCallStack, PrimMonad m, Monoid a, Unbox a) => DenseSegTree2d (PrimState m) a -> Int -> Int -> Int -> Int -> m a
allProd :: (HasCallStack, PrimMonad m, Monoid a, Unbox a) => DenseSegTree2d (PrimState m) a -> m a

DenseSegTree2d

data DenseSegTree2d s a Source #

Two-dimensional segment tree.

Since: 1.2.3.0

Constructors

DenseSegTree2d
Fields hDst :: !Int Height Since: 1.2.3.0 wDst :: !Int Width Since: 1.2.3.0 dataDst :: !(MVector s a) Monoid values Since: 1.2.3.0

Constructors

new Source #

Arguments

:: (PrimMonad m, Monoid a, Unbox a)
=> Int	Width
-> Int	Height
-> m (DenseSegTree2d (PrimState m) a)	Dense, two-dimensional segment tree

\(O(hw)\) Creates a DenseSegTree2d for \([0, w) \times [0, h)\) from \(w\) and \(h\).

Since: 1.2.3.0

build Source #

Arguments

:: (HasCallStack, PrimMonad m, Monoid a, Unbox a)
=> Int	Width
-> Int	Height
-> Vector a	Vector of monoid values
-> m (DenseSegTree2d (PrimState m) a)	Dense, two-dimensional segment tree

\(O(hw)\) Creates a DenseSegTree2d from width, height and one-dimensional vector of monoid values.

Since: 1.2.3.0

build' Source #

Arguments

:: (HasCallStack, PrimMonad m, Monoid a, Unbox a)
=> Vector (Vector a)	Two-dimensional vector of monoid values
-> m (DenseSegTree2d (PrimState m) a)	Dense, two-dimensional segment tree

\(O(hw)\) Creates a DenseSegTree2d from a two-dimensional vector of monoid values. The vector must be indexed by \(y\) first then \(x\): vec V.! y VU.! x.

Constraints

The length of the monoid value vector must be \(hw\).

Since: 1.2.3.0

Read

read :: (HasCallStack, PrimMonad m, Monoid a, Unbox a) => DenseSegTree2d (PrimState m) a -> Int -> Int -> m a Source #

\(O(1)\) Returns the monoid value at \((x, y)\).

Since: 1.2.3.0

readMaybe :: (HasCallStack, PrimMonad m, Monoid a, Unbox a) => DenseSegTree2d (PrimState m) a -> Int -> Int -> m (Maybe a) Source #

\(O(1)\) Returns the monoid value at \((x, y)\), or Nothing if the point is out of the bounds.

Since: 1.2.3.0

Write

write :: (HasCallStack, PrimMonad m, Monoid a, Unbox a) => DenseSegTree2d (PrimState m) a -> Int -> Int -> a -> m () Source #

\(O(\log h \log w)\) Writes to the \(k\)-th original point's monoid value.

Since: 1.2.3.0

modify :: (HasCallStack, PrimMonad m, Monoid a, Unbox a) => DenseSegTree2d (PrimState m) a -> (a -> a) -> Int -> Int -> m () Source #

\(O(\log h \log w)\) Given a user function \(f\), modifies the monoid value at \((x, y)\) with it.

Since: 1.2.3.0

modifyM :: (HasCallStack, PrimMonad m, Monoid a, Unbox a) => DenseSegTree2d (PrimState m) a -> (a -> m a) -> Int -> Int -> m () Source #

\(O(\log h \log w)\) Given a user function \(f\), modifies the monoid value at \((x, y)\) with it.

Since: 1.2.3.0

Monoid product

prod :: (HasCallStack, PrimMonad m, Monoid a, Unbox a) => DenseSegTree2d (PrimState m) a -> Int -> Int -> Int -> Int -> m a Source #

\(O(\log h \log w)\) Returns monoid product \(\Pi_{p \in [x_1, x_2) \times [y_1, y_2)} a_p\).

Since: 1.2.3.0

allProd :: (HasCallStack, PrimMonad m, Monoid a, Unbox a) => DenseSegTree2d (PrimState m) a -> m a Source #

\(O(1)\) Returns monoid product \(\Pi_{p \in [0, w) \times [0, h)} a_p\).

Since: 1.2.3.0