FenwickTree- Data structure for fast query and update of cumulative sums

Safe HaskellSafe-Inferred




data FTree a Source

Mother structure holds functions that allow to get a value to be summed and comparison function. Below there is a tree of FNodes.


Show a => Show (FTree a) 

empty :: (a -> Double) -> (a -> a -> Ordering) -> FTree a Source

Creates an empty Fenwick tree.

insert :: a -> FTree a -> FTree a Source

Inserts a value into a Fenwick tree.

query :: a -> FTree a -> Val Source

Finds a cumulative sum up to a given node of a Fenwick tree. Note: if the node is not found, a sum at point corresponding to this node is still returned. (Convenient for finding CDF value at a given point.)

invQuery :: Val -> FTree a -> Maybe a Source

Finds a node corresponding to a given cumulative sum, convenient for sampling quantile function of a distribution. NOTE: returns an answer only up to a cumulative sum of a whole tree.

toList :: FTree a -> [a] Source

Extract a sorted list of inserted values from the tree.

toFreqList :: FTree a -> [(Double, a)] Source

Extract a sorted list of cumulative sums, and corresponding objects from the tree.

fromList :: (a -> a -> Ordering) -> (a -> Val) -> [a] -> FTree a Source

Creates a tree from a list and helper functions: compare, and value.

size :: FTree a -> Int Source

Returns number of elements in a tree.

depth :: FTree a -> Int Source

Returns a maximum depth of a tree.