Safe Haskell	None
Language	GHC2021

Data.FenwickTree.Sum

Synopsis

newtype SumFenwickTree s a = SumFenwickTree {
- getSumFenwickTree :: MVector s a
}
newSumFenwickTree :: (Unbox a, Num a, PrimMonad m) => Int -> m (SumFenwickTree (PrimState m) a)
buildSumFenwickTree :: (Unbox a, Num a, PrimMonad m) => Vector a -> m (SumFenwickTree (PrimState m) a)
sumTo :: (PrimMonad m, Unbox a, Num a) => SumFenwickTree (PrimState m) a -> Int -> m a
sumFromTo :: (PrimMonad m, Unbox a, Num a) => SumFenwickTree (PrimState m) a -> Int -> Int -> m a
addAt :: (Unbox a, Num a, PrimMonad m) => SumFenwickTree (PrimState m) a -> Int -> a -> m ()
readSFT :: (Num a, Unbox a, PrimMonad m) => SumFenwickTree (PrimState m) a -> Int -> m a
writeSFT :: (Num a, Unbox a, PrimMonad m) => SumFenwickTree (PrimState m) a -> Int -> a -> m ()
lowerBoundSFT :: (Unbox a, Num a, Ord a, PrimMonad m) => SumFenwickTree (PrimState m) a -> a -> m Int
upperBoundSFT :: (Unbox a, Num a, Ord a, PrimMonad m) => SumFenwickTree (PrimState m) a -> a -> m Int

Documentation

newtype SumFenwickTree s a Source #

Constructors

SumFenwickTree
Fields getSumFenwickTree :: MVector s a

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

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

O(n)

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

sum[0..k)

O(log n)

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

sum[l..r)

O(log n)

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

O(log n)

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

O(log n)

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

O(log n)

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

min i s.t. sum [0..i) >= w

>>> ft <- buildSumFenwickTree @Int (U.fromList [1,1,1,1,1])
>>> lowerBoundSFT ft 3
3
>>> sumTo ft 3
3
>>> lowerBoundSFT ft 0
0
>>> lowerBoundSFT ft 1
1
>>> lowerBoundSFT ft 10
6

>>> ft <- buildSumFenwickTree @Int (U.fromList [1,1,0,0,0])
>>> lowerBoundSFT ft 2
2

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

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

>>> ft <- buildSumFenwickTree @Int (U.fromList [1,1,1,1,1])
>>> upperBoundSFT ft 3
3
>>> sumTo ft 3
3
>>> upperBoundSFT ft 0
0
>>> upperBoundSFT ft 1
1
>>> upperBoundSFT ft 10
5

>>> ft <- buildSumFenwickTree @Int (U.fromList [1,1,0,0,1])
>>> upperBoundSFT ft 2
4