| Safe Haskell | Safe-Inferred |
|---|---|
| Language | GHC2021 |
AtCoder.Extra.SegTree2d
Description
Two-dimensional segment tree for commutative monoids at fixed points.
SegTree2d vs WaveletMatrix2d
They basically have the same functionalities and performance, however, SegTree2d performs better in
ac-library-hs.
Examples
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 2Sum {getSum = 30}
Monoid values can be altered:
>>>Seg.write seg 1 50>>>Seg.prod seg {- x -} 1 2 {- y -} 1 2Sum {getSum = 50}
>>>Seg.allProd segSum {getSum = 60}
>>>Seg.count seg {- x -} 0 2 {- y -} 0 22
Since: 1.2.3.0
Synopsis
- data SegTree2d s a = SegTree2d {}
- 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
Two-dimensional segment tree.
Since: 1.2.3.0
Constructors
| SegTree2d | |
Fields
| |
Constructors
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
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
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
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
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
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
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
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