Safe Haskell	Safe-Inferred
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 $f$ , modofies the monoid value at $(x, y)$ .

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 $f$ , modofies the monoid value at $(x, y)$ .

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

Key	Shortcut
s	Open this search box
esc	Close this search box
↓,ctrl + j	Move down in search results
↑,ctrl + k	Move up in search results
↵	Go to active search result