Safe Haskell	Safe-Inferred
Language	GHC2021

AtCoder.Extra.SegTree2d

Contents

SegTree2d
Constructors
Write
Monoid product
Count

Description

Two-dimensional segment tree for commutative monoids at fixed points.

SegTree2d vs WaveletMatrix2d

They basically the same functionalities and performance, however, in ac-library-hs, SegTree2d has better API and even outperforms WaveletMatrix2d.

Examples

Expand

Create a two-dimensional segment tree for points $(0, 0)$ with weight $10$ and $(1, 1)$ with weight $20$ :

>>> import AtCoder.Extra.SegTree2d qualified as Seg
>>> import Data.Semigroup (Sum (..))
>>> import Data.Vector.Unboxed qualified as VU
>>> seg <- Seg.build3 @_ @(Sum Int) $ VU.fromList [(0, 0, 10), (1, 1, 20)]

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

>>> Seg.prod seg {- x -} 0 2 {- y -} 0 2
Sum {getSum = 30}

Monoid values can be altered:

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

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

>>> Seg.count seg {- x -} 0 2 {- y -} 0 2
2

Since: 1.2.3.0

Synopsis

data SegTree2d s a = SegTree2d {
- nSt :: !Int
- nxSt :: !Int
- logSt :: !Int
- sizeSt :: !Int
- dictXSt :: !(Vector Int)
- allYSt :: !(Vector Int)
- posSt :: !(Vector Int)
- indptrSt :: !(Vector Int)
- dataSt :: !(MVector s a)
- toLeftSt :: !(Vector Int)
}
new :: (PrimMonad m, Monoid a, Unbox a) => Vector (Int, Int) -> m (SegTree2d (PrimState m) a)
build :: (HasCallStack, PrimMonad m, Monoid a, Unbox a) => Vector Int -> Vector Int -> Vector a -> m (SegTree2d (PrimState m) a)
build2 :: (HasCallStack, PrimMonad m, Monoid a, Unbox a) => Vector (Int, Int) -> Vector a -> m (SegTree2d (PrimState m) a)
build3 :: (HasCallStack, PrimMonad m, Monoid a, Unbox a) => Vector (Int, Int, a) -> m (SegTree2d (PrimState m) a)
write :: (HasCallStack, PrimMonad m, Monoid a, Unbox a) => SegTree2d (PrimState m) a -> Int -> a -> m ()
modify :: (HasCallStack, PrimMonad m, Monoid a, Unbox a) => SegTree2d (PrimState m) a -> (a -> a) -> Int -> m ()
modifyM :: (HasCallStack, PrimMonad m, Monoid a, Unbox a) => SegTree2d (PrimState m) a -> (a -> m a) -> Int -> m ()
prod :: (HasCallStack, PrimMonad m, Monoid a, Unbox a) => SegTree2d (PrimState m) a -> Int -> Int -> Int -> Int -> m a
allProd :: (HasCallStack, PrimMonad m, Monoid a, Unbox a) => SegTree2d (PrimState m) a -> m a
count :: (HasCallStack, PrimMonad m, Monoid a, Unbox a) => SegTree2d (PrimState m) a -> Int -> Int -> Int -> Int -> m Int

SegTree2d

data SegTree2d s a Source #

Two-dimensional segment tree.

Since: 1.2.3.0

Constructors

SegTree2d

Fields

nSt :: !Int
The number of nodes.
Since: 1.2.3.0
nxSt :: !Int
The number of distinct $x$ coordinates.
Since: 1.2.3.0
logSt :: !Int
$\lceil \log_2 (\mathrm{nx} + 1) \rceil$
Since: 1.2.3.0
sizeSt :: !Int
$2^{\mathrm{logSt}}$
Since: 1.2.3.0
dictXSt :: !(Vector Int)
$x$ coordinates sorted and uniquified
Since: 1.2.3.0
allYSt :: !(Vector Int)
$y$ coordinates sorted (not uniquified)
Since: 1.2.3.0
posSt :: !(Vector Int)
Since: 1.2.3.0
indptrSt :: !(Vector Int)
Since: 1.2.3.0
dataSt :: !(MVector s a)
Monoid values
Since: 1.2.3.0
toLeftSt :: !(Vector Int)
Since: 1.2.3.0

Constructors

new Source #

Arguments

:: (PrimMonad m, Monoid a, Unbox a)
=> Vector (Int, Int)	$(x, y)$ vector
-> m (SegTree2d (PrimState m) a)	Two-dimensional segment tree

$O(n \log n)$ Creates a SegTree2d from a vector of $(x, y)$ coordinates.

Since: 1.2.3.0

build Source #

Arguments

:: (HasCallStack, PrimMonad m, Monoid a, Unbox a)
=> Vector Int	$x$ vector
-> Vector Int	$y$ vector
-> Vector a	$w$ vector
-> m (SegTree2d (PrimState m) a)	Two-dimensional segment tree

$O(n \log n)$ Creates a SegTree2d from vectors of $x$ , $y$ and $w$ .

Since: 1.2.3.0

build2 Source #

Arguments

:: (HasCallStack, PrimMonad m, Monoid a, Unbox a)
=> Vector (Int, Int)	$(x, y)$ vector
-> Vector a	$w$ vector
-> m (SegTree2d (PrimState m) a)	Two-dimensional segment tree

$O(n \log n)$ Creates a SegTree2d from vectors of $(x, y)$ and $w$ .

Since: 1.2.3.0

build3 :: (HasCallStack, PrimMonad m, Monoid a, Unbox a) => Vector (Int, Int, a) -> m (SegTree2d (PrimState m) a) Source #

$O(n \log n)$ Creates a SegTree2d from a vector of $(x, y, w)$ .

Since: 1.2.3.0

Write

write Source #

Arguments

:: (HasCallStack, PrimMonad m, Monoid a, Unbox a)
=> SegTree2d (PrimState m) a	Two-dimensional segment tree
-> Int	Original point index
-> a	New monoid value
-> m ()

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

Since: 1.2.3.0

modify Source #

Arguments

:: (HasCallStack, PrimMonad m, Monoid a, Unbox a)
=> SegTree2d (PrimState m) a	Two-dimensional segment tree
-> (a -> a)	Function that alters the monoid value
-> Int	Original point index
-> m ()

$O(\log n)$ Given $f$ , modofies the $k$ -th original point's monoid value.

Since: 1.2.3.0

modifyM Source #

Arguments

:: (HasCallStack, PrimMonad m, Monoid a, Unbox a)
=> SegTree2d (PrimState m) a	Two-dimensional segment tree
-> (a -> m a)	Function that alters the monoid value
-> Int	Original point index
-> m ()

$O(\log n)$ Given $f$ , modofies the $k$ -th original point's monoid value.

Since: 1.2.3.0

Monoid product

prod Source #

Arguments

:: (HasCallStack, PrimMonad m, Monoid a, Unbox a)
=> SegTree2d (PrimState m) a	Two-dimensional segment tree
-> 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(\log^2 n)$ 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) => SegTree2d (PrimState m) a -> m a Source #

$O(1)$ Returns monoid product $\Pi_{p \in [-\infty, \infty) \times [-\infty, \infty)} a_p$ .

Since: 1.2.3.0

Count

count Source #

Arguments

:: (HasCallStack, PrimMonad m, Monoid a, Unbox a)
=> SegTree2d (PrimState m) a	Two-dimensional segment tree
-> Int	$x_1$
-> Int	$x_2$
-> Int	$y_1$
-> Int	$y_2$
-> m Int	The number of points in $[x_1, x_2) \times [y_1, y_2)$

$O(\log n)$ Returns the number of points in $[x_1, x_2) \times [y_1, y_2)$ .

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