Safe Haskell	Safe-Inferred
Language	GHC2021

AtCoder.SegTree

Contents

Segment tree
Constructors
Accessing elements
Products
Binary searches
- Left binary searches
- Right binary searches
Conversions

Description

It is the data structure for monoids $(S, \cdot: S \times S \to S, e \in S)$ , i.e., the algebraic structure that satisfies the following properties.

associativity: $(a \cdot b) \cdot c$ = $a \cdot (b \cdot c)$ for all $a, b, c \in S$
existence of the identity element: $a \cdot e$ = $e \cdot a$ = $a$ for all $a \in S$

Given an array $S$ of length $N$ , it processes the following queries in $O(\log N)$ time (see Appendix for further details).

Updating an element
Calculating the product of the elements of an interval

For simplicity, in this document, we assume that the oracles op and e work in constant time. If these oracles work in $O(T)$ time, each time complexity appear in this document is multipled by $O(T)$ .

Example

Expand

Create a SegTree of Sum Int:

>>> import AtCoder.SegTree qualified as ST
>>> import Data.Vector.Unboxed qualified as VU
>>> import Data.Monoid (Sum(..))
>>> seg <- ST.new @_ @(Sum Int) 4

Modify the vertex values:

>>> ST.write seg 1 $ Sum 1
>>> ST.modify seg (+ Sum 2) 2
>>> ST.write seg 3 $ Sum 3 -- [0, 1, 2, 3]
>>> ST.read seg 1
Sum {getSum = 1}

Get product of the monoids:

>>> ST.prod seg 0 3
Sum {getSum = 3}

>>> ST.allProd seg
Sum {getSum = 6}

Binary searches:

>>> ST.maxRight seg 0 (< (Sum 5)) -- sum [0, 3) = 2 < 5
3

>>> ST.minLeft seg 4 (< (Sum 5)) -- sum [3, 4) = 3 < 5
3

Inspect all the values in $O(n)$ with freeze or in $O(1)$ with unsafeFreeze:

>>> VU.map getSum <$> ST.freeze seg
[0,1,2,3]

Tips

prod returns $a_l \cdot a_{l + 1} \cdot .. \cdot a_{r - 1}$ . If you need $a_{r - 1} \cdot a_{r - 2} \cdot .. \cdot a_{l}$ , wrap your monoid in Dual.
If you ever need to store boxed types to LazySegTree, wrap it in Data.Vector.Unboxed.DoNotUnboxStrict or the like.

Major changes from the original `ac-library`

The implementation is Monoid based, not function objects.
get and set are renamed to read and write.
modify, modifyM, exchange, freeze and unsafeFreeze are added.

Since: 1.0.0.0

Synopsis

data SegTree s a
new :: (HasCallStack, PrimMonad m, Monoid a, Unbox a) => Int -> m (SegTree (PrimState m) a)
build :: (PrimMonad m, Monoid a, Unbox a) => Vector a -> m (SegTree (PrimState m) a)
write :: (HasCallStack, PrimMonad m, Monoid a, Unbox a) => SegTree (PrimState m) a -> Int -> a -> m ()
modify :: (HasCallStack, PrimMonad m, Monoid a, Unbox a) => SegTree (PrimState m) a -> (a -> a) -> Int -> m ()
modifyM :: (HasCallStack, PrimMonad m, Monoid a, Unbox a) => SegTree (PrimState m) a -> (a -> m a) -> Int -> m ()
exchange :: (HasCallStack, PrimMonad m, Monoid a, Unbox a) => SegTree (PrimState m) a -> Int -> a -> m a
read :: (HasCallStack, PrimMonad m, Monoid a, Unbox a) => SegTree (PrimState m) a -> Int -> m a
prod :: (HasCallStack, PrimMonad m, Monoid a, Unbox a) => SegTree (PrimState m) a -> Int -> Int -> m a
prodMaybe :: (HasCallStack, PrimMonad m, Monoid a, Unbox a) => SegTree (PrimState m) a -> Int -> Int -> m (Maybe a)
allProd :: (PrimMonad m, Monoid a, Unbox a) => SegTree (PrimState m) a -> m a
minLeft :: (HasCallStack, PrimMonad m, Monoid a, Unbox a) => SegTree (PrimState m) a -> Int -> (a -> Bool) -> m Int
minLeftM :: (HasCallStack, PrimMonad m, Monoid a, Unbox a) => SegTree (PrimState m) a -> Int -> (a -> m Bool) -> m Int
maxRight :: (HasCallStack, PrimMonad m, Monoid a, Unbox a) => SegTree (PrimState m) a -> Int -> (a -> Bool) -> m Int
maxRightM :: (HasCallStack, PrimMonad m, Monoid a, Unbox a) => SegTree (PrimState m) a -> Int -> (a -> m Bool) -> m Int
freeze :: (PrimMonad m, Unbox a) => SegTree (PrimState m) a -> m (Vector a)
unsafeFreeze :: (PrimMonad m, Unbox a) => SegTree (PrimState m) a -> m (Vector a)

Segment tree

data SegTree s a Source #

Segment tree.

Since: 1.0.0.0

Constructors

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

Creates an array $a$ of length $n$ . All the elements are initialized to mempty.

Constraints

$0 \leq n$

Complexity

$O(n)$

Since: 1.0.0.0

build :: (PrimMonad m, Monoid a, Unbox a) => Vector a -> m (SegTree (PrimState m) a) Source #

Creates an array with initial values.

Complexity

$O(n)$

Since: 1.0.0.0

Accessing elements

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

Writes $p$ -th value of the array to $x$ .

Constraints

$0 \leq p \lt n$

Complexity

$O(\log n)$

Since: 1.0.0.0

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

(Extra API) Modifies $p$ -th value with a function $f$ .

Constraints

$0 \leq p \lt n$

Complexity

$O(\log n)$

Since: 1.0.0.0

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

(Extra API) Modifies $p$ -th value with a monadic function $f$ .

Constraints

$0 \leq p \lt n$

Complexity

$O(\log n)$

Since: 1.0.0.0

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

(Extra API) Writes $p$ -th value of the array to $x$ and returns the old value.

Constraints

$0 \leq p \lt n$

Complexity

$O(\log n)$

Since: 1.1.0.0

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

Returns $p$ -th value of the array.

Constraints

$0 \leq p \lt n$

Complexity

$O(1)$

Since: 1.0.0.0

Products

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

Returns $a[l] \cdot ... \cdot a[r - 1]$ , assuming the properties of the monoid. It returns mempty if $l = r$ .

Constraints

$0 \leq l \leq r \leq n$

Complexity

$O(\log n)$

Since: 1.0.0.0

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

Total variant of prod. Returns $a[l] \cdot ... \cdot a[r - 1]$ , assuming the properties of the monoid. It returns Just mempty if $l = r$ . Returns Nothing if the interval is invalid.

Complexity

$O(\log n)$

Since: 1.0.0.0

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

Returns a[0] <> ... <> a[n - 1], assuming the properties of the monoid. It returns mempty if $n = 0$ .

Complexity

$O(1)$

Since: 1.0.0.0

Binary searches

Left binary searches

minLeft Source #

Arguments

:: (HasCallStack, PrimMonad m, Monoid a, Unbox a)
=> SegTree (PrimState m) a	The segment tree
-> Int	$r$
-> (a -> Bool)	$p$ : user prediate
-> m Int	$l$ : $p$ holds for $[l, r)$

Applies a binary search on the segment tree. It returns an index $l$ that satisfies both of the following.

$l = r$ or $f(a[l] \cdot a[l + 1] \cdot ... \cdot a[r - 1])$ returns True.
$l = 0$ or $f(a[l - 1] \cdot a[l] \cdot ... \cdot a[r - 1])$ returns False.

If $f$ is monotone, this is the minimum $l$ that satisfies $f(a[l] \cdot a[l + 1] \cdot ... \cdot a[r - 1])$ .

Constraints

if $f$ is called with the same argument, it returns the same value, i.e., $f$ has no side effect.
f mempty == True.
$0 \leq r \leq n$

Complexity

$O(\log n)$

Since: 1.0.0.0

minLeftM Source #

Arguments

:: (HasCallStack, PrimMonad m, Monoid a, Unbox a)
=> SegTree (PrimState m) a	The segment tree
-> Int	$r$
-> (a -> m Bool)	$p$ : user prediate
-> m Int	$l$ : $p$ holds for $[l, r)$

Monadic variant of minLeft.

Constraints

if $f$ is called with the same argument, it returns the same value, i.e., $f$ has no side effect.
f mempty == True.
$0 \leq r \leq n$

Complexity

$O(\log n)$

Since: 1.0.0.0

Right binary searches

maxRight Source #

Arguments

:: (HasCallStack, PrimMonad m, Monoid a, Unbox a)
=> SegTree (PrimState m) a	The segment tree
-> Int	$l$
-> (a -> Bool)	$p$ : user prediate
-> m Int	$r$ : $p$ holds for $[l, r)$

Applies a binary search on the segment tree. It returns an index $r$ that satisfies both of the following.

$r = l$ or $f(a[l] \cdot a[l + 1] \cdot ... \cdot a[r - 1])$ returns True.
$r = n$ or $f(a[l] \cdot a[l + 1] \cdot ... \cdot a[r]))$ returns False.

If $f$ is monotone, this is the maximum $r$ that satisfies $f(a[l] \cdot a[l + 1] \cdot ... \cdot a[r - 1])$ .

Constraints

if $f$ is called with the same argument, it returns the same value, i.e., $f$ has no side effect.
f mempty == True.
$0 \leq l \leq n$

Complexity

$O(\log n)$

Since: 1.0.0.0

maxRightM Source #

Arguments

:: (HasCallStack, PrimMonad m, Monoid a, Unbox a)
=> SegTree (PrimState m) a	The segment tree
-> Int	$l$
-> (a -> m Bool)	$p$ : user prediate
-> m Int	$r$ : $p$ holds for $[l, r)$

Moandic variant of maxRight.

Constraints

if $f$ is called with the same argument, it returns the same value, i.e., $f$ has no side effect.
f mempty == True.
$0 \leq l \leq n$

Complexity

$O(\log n)$

Since: 1.0.0.0

Conversions

freeze :: (PrimMonad m, Unbox a) => SegTree (PrimState m) a -> m (Vector a) Source #

$O(n)$ Yields an immutable copy of the mutable vector.

Since: 1.0.0.0

unsafeFreeze :: (PrimMonad m, Unbox a) => SegTree (PrimState m) a -> m (Vector a) Source #

$O(1)$ Unsafely converts a mutable vector to an immutable one without copying. The mutable vector may not be used after this operation.

Since: 1.0.0.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

Example

Tips

Major changes from the original ac-library

Segment tree

Constructors

Constraints

Complexity

Complexity

Accessing elements

Constraints

Complexity

Constraints

Complexity

Constraints

Complexity

Constraints

Complexity

Constraints

Complexity

Products

Constraints

Complexity

Complexity

Complexity

Binary searches

Left binary searches

Constraints

Complexity

Constraints

Complexity

Right binary searches

Constraints

Complexity

Constraints

Complexity

Conversions

Major changes from the original `ac-library`