- data FTree a
- empty :: (a -> Double) -> (a -> a -> Ordering) -> FTree a
- insert :: a -> FTree a -> FTree a
- query :: a -> FTree a -> Val
- invQuery :: Val -> FTree a -> Maybe a
- toList :: FTree a -> [a]
- toFreqList :: FTree a -> [(Double, a)]
- fromList :: (a -> a -> Ordering) -> (a -> Val) -> [a] -> FTree a
- size :: FTree a -> Int
- depth :: FTree a -> Int
Mother structure holds functions
that allow to get a value to be summed and comparison function.
Below there is a tree of
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.)
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.
Extract a sorted list of cumulative sums, and corresponding objects from the tree.
Creates a tree from a list and helper functions: compare, and value.