| Safe Haskell | Safe-Inferred |
|---|---|
| Language | Haskell2010 |
Data.WaveletMatrix.SegTree
Description
Segment Tree on Wavelet Matrix: points on a 2D plane and rectangle folding.
Typical problems
FIXME: My wavelet matrix is somehow slow.
Synopsis
- data WaveletMatrixSegTree s a = WaveletMatrixSegTree {
- rawWmWMST :: !RawWaveletMatrix
- xysWMST :: !(Vector (Int, Int))
- ysWMST :: !(Vector Int)
- segTreesWMST :: !(Vector (SegmentTree s a))
- buildWMST :: (Monoid a, Unbox a, PrimMonad m) => Vector (Int, Int) -> m (WaveletMatrixSegTree (PrimState m) a)
- modifyWMST :: (Monoid a, Unbox a, PrimMonad m) => WaveletMatrixSegTree (PrimState m) a -> (a -> a) -> (Int, Int) -> m ()
- _foldLTWMST :: (Monoid a, Unbox a, PrimMonad m) => WaveletMatrixSegTree (PrimState m) a -> Int -> Int -> Int -> m a
- foldMayWMST :: (Group a, Unbox a, PrimMonad m) => WaveletMatrixSegTree (PrimState m) a -> Int -> Int -> Int -> Int -> m (Maybe a)
- indexXWMST :: WaveletMatrixSegTree s a -> Int -> Int
- indexYWMST :: WaveletMatrixSegTree s a -> Int -> Int
- indexXYWMST :: WaveletMatrixSegTree s a -> Int -> Int -> (Int, Int)
Documentation
data WaveletMatrixSegTree s a #
Segment Tree on Wavelet Matrix: points on a 2D plane and rectangle folding.
Constructors
| WaveletMatrixSegTree | |
Fields
| |
buildWMST :: (Monoid a, Unbox a, PrimMonad m) => Vector (Int, Int) -> m (WaveletMatrixSegTree (PrimState m) a) #
\(O(N (\log N + \log A)\) Creates a 2D wavelet matrix.
modifyWMST :: (Monoid a, Unbox a, PrimMonad m) => WaveletMatrixSegTree (PrimState m) a -> (a -> a) -> (Int, Int) -> m () #
\(O(N (\log N + \log A)\) Modifies a point. Access to unknown points are undefined.
_foldLTWMST :: (Monoid a, Unbox a, PrimMonad m) => WaveletMatrixSegTree (PrimState m) a -> Int -> Int -> Int -> m a #
\(O(\log^2 N)\) Folding.
foldMayWMST :: (Group a, Unbox a, PrimMonad m) => WaveletMatrixSegTree (PrimState m) a -> Int -> Int -> Int -> Int -> m (Maybe a) #
\(O(\log^2 N)\) Folding.
indexXWMST :: WaveletMatrixSegTree s a -> Int -> Int #
\(O(\log N)\) Index restoration. Access to unknown points are undefined.
indexYWMST :: WaveletMatrixSegTree s a -> Int -> Int #
\(O(\log N)\) Index restoration. Access to unknown points are undefined.
indexXYWMST :: WaveletMatrixSegTree s a -> Int -> Int -> (Int, Int) #
\(O(\log N)\) Index restoration. Access to unknown points are undefined.