ac-library-hs-0.1.0.0: Data structures and algorithms
Safe HaskellNone
LanguageGHC2021

AtCoder.SegTree

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.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 SegTree, wrap it in DoNotUnboxStrict or the like.

Major changes from the original ac-library

Since: 1.0.0

Synopsis

Segment tree

data SegTree s a #

Segment tree.

Since: 1.0.0

Constructors

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

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

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

Creates an array with initial values.

Complexity

  • \(O(n)\)

Since: 1.0.0

Accessing individual elements

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

Writes \(p\)-th value of the array to \(x\).

Constraints

  • \(0 \leq p \lt n\)

Complexity

  • \(O(\log n)\)

Since: 1.0.0

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

(Extra API) Modifies \(p\)-th value of the array to \(x\).

Constraints

  • \(0 \leq p \lt n\)

Complexity

  • \(O(\log n)\)

Since: 1.0.0

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

(Extra API) Modifies \(p\)-th value of the array to \(x\).

Constraints

  • \(0 \leq p \lt n\)

Complexity

  • \(O(\log n)\)

Since: 1.0.0

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

Returns \(p\)-th value of the array.

Constraints

  • \(0 \leq p \lt n\)

Complexity

  • \(O(1)\)

Since: 1.0.0

Products

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

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

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

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

Binary searches

Left binary searches

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

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

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

Moandic version 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

Right binary searches

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

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

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

Monadic version 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

Conversions

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

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

Since: 1.0.0

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

\(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