Safe Haskell	None
Language	GHC2021

Data.FenwickTree.RangeAdd

Synopsis

newtype RangeAddFenwickTree s a = RangeAddFenwickTree (MVector s a)
newRangeAddFenwickTree :: (Num a, Unbox a, PrimMonad m) => Int -> m (RangeAddFenwickTree (PrimState m) a)
buildRangeAddFenwickTree :: (Num a, Unbox a, PrimMonad m) => Vector a -> m (RangeAddFenwickTree (PrimState m) a)
addFromTo :: (Num a, Unbox a, PrimMonad m) => RangeAddFenwickTree (PrimState m) a -> Int -> Int -> a -> m ()
readRAFT :: (Num a, Unbox a, PrimMonad m) => RangeAddFenwickTree (PrimState m) a -> Int -> m a
writeRAFT :: (Num a, Unbox a, PrimMonad m) => RangeAddFenwickTree (PrimState m) a -> Int -> a -> m ()
lowerBoundRAFT :: (Unbox a, Num a, Ord a, PrimMonad m) => RangeAddFenwickTree (PrimState m) a -> a -> m Int
upperBoundRAFT :: (Unbox a, Num a, Ord a, PrimMonad m) => RangeAddFenwickTree (PrimState m) a -> a -> m Int

Documentation

Constructors

newRangeAddFenwickTree :: (Num a, Unbox a, PrimMonad m) => Int -> m (RangeAddFenwickTree (PrimState m) a) Source #

buildRangeAddFenwickTree :: (Num a, Unbox a, PrimMonad m) => Vector a -> m (RangeAddFenwickTree (PrimState m) a) Source #

addFromTo :: (Num a, Unbox a, PrimMonad m) => RangeAddFenwickTree (PrimState m) a -> Int -> Int -> a -> m () Source #

readRAFT :: (Num a, Unbox a, PrimMonad m) => RangeAddFenwickTree (PrimState m) a -> Int -> m a Source #

O(log n)

writeRAFT :: (Num a, Unbox a, PrimMonad m) => RangeAddFenwickTree (PrimState m) a -> Int -> a -> m () Source #

O(log n)

lowerBoundRAFT :: (Unbox a, Num a, Ord a, PrimMonad m) => RangeAddFenwickTree (PrimState m) a -> a -> m Int Source #

>>> ft <- buildRangeAddFenwickTree @Int (U.fromList [1,2,2,3,3,3])
>>> lowerBoundRAFT ft 2
1
>>> lowerBoundRAFT ft 0
0
>>> lowerBoundRAFT ft 10
6

upperBoundRAFT :: (Unbox a, Num a, Ord a, PrimMonad m) => RangeAddFenwickTree (PrimState m) a -> a -> m Int Source #

>>> ft <- buildRangeAddFenwickTree @Int (U.fromList [1,2,2,3,3,3])
>>> upperBoundRAFT ft 2
3
>>> upperBoundRAFT ft 0
0
>>> upperBoundRAFT ft 10
6