Safe Haskell	Safe-Inferred
Language	GHC2021

Data.FenwickTree

Synopsis

newtype FenwickTree s a = FenwickTree {
- getFenwickTree :: MVector s a
}
newFenwickTree :: (Unbox a, Monoid a, PrimMonad m) => Int -> m (FenwickTree (PrimState m) a)
buildFenwickTree :: (Unbox a, Monoid a, PrimMonad m) => Vector a -> m (FenwickTree (PrimState m) a)
mappendTo :: (PrimMonad m, Unbox a, Monoid a) => FenwickTree (PrimState m) a -> Int -> m a
mappendAt :: (Unbox a, Semigroup a, PrimMonad m) => FenwickTree (PrimState m) a -> Int -> a -> m ()
type SumFenwickTree s a = FenwickTree s (Sum a)
newSumFenwickTree :: (Num a, Unbox a, PrimMonad m) => Int -> m (SumFenwickTree (PrimState m) a)
buildSumFenwickTree :: (Num a, Unbox a, PrimMonad m) => Vector a -> m (SumFenwickTree (PrimState m) a)
sumTo :: (Num a, Unbox a, PrimMonad m) => SumFenwickTree (PrimState m) a -> Int -> m a
sumFromTo :: (Num a, Unbox a, PrimMonad m) => SumFenwickTree (PrimState m) a -> Int -> Int -> m a
readSumFenwickTree :: (Num a, Unbox a, PrimMonad m) => SumFenwickTree (PrimState m) a -> Int -> m a
writeSumFenwickTree :: (Num a, Unbox a, PrimMonad m) => SumFenwickTree (PrimState m) a -> Int -> a -> m ()
addAt :: (Unbox a, Num a, PrimMonad m) => SumFenwickTree (PrimState m) a -> Int -> a -> m ()
findMaxIndexLT :: (Unbox a, Num a, Ord a, PrimMonad m) => FenwickTree (PrimState m) a -> a -> m Int

Documentation

newtype FenwickTree s a Source #

Constructors

FenwickTree
Fields getFenwickTree :: MVector s a

newFenwickTree :: (Unbox a, Monoid a, PrimMonad m) => Int -> m (FenwickTree (PrimState m) a) Source #

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

O(n)

mappendTo :: (PrimMonad m, Unbox a, Monoid a) => FenwickTree (PrimState m) a -> Int -> m a Source #

mappend [0..k)

O(log n)

mappendAt :: (Unbox a, Semigroup a, PrimMonad m) => FenwickTree (PrimState m) a -> Int -> a -> m () Source #

O(log n)

type SumFenwickTree s a = FenwickTree s (Sum a) Source #

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

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

O(n)

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

sum [0..k)

O(log n)

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

sum [l..r)

O(log n)

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

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

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

O(log n)

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

max i s.t. sum [0..i) < w

findMaxIndexLT k [1, 1..1] == k - 1

>>> ones <- buildFenwickTree [1, 1, 1, 1, 1]
>>> findMaxIndexLT 3 ones
2
>>> findMaxIndexLT 0 ones
0
>>> ids <- buildFenwickTree [1, 2, 3, 4, 5]
>>> findMaxIndexLT 6 ids
2
>>> findMaxIndexLT 7 ids
3
>>> zeros <- buildFenwickTree [0, 0, 0, 0, 0]
>>> findMaxIndexLT 1 zeros
5