| Safe Haskell | None |
|---|---|
| Language | Haskell2010 |
Fenwick
Description
Fenwick tree, or binary indexed tree
A data structure supporting point updates and range queries, or the opposite. Large ranges, beyond typical memory limits, are supported. See FenwickMut.hs for a mutable (and more commonly seen) version.
Sources:
- https://en.wikipedia.org/wiki/Fenwick_tree
- Peter M. Fenwick, "A New Data Structure for Cumulative Frequency Tables", 1994 https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.14.8917
- https://hackage.haskell.org/package/binary-indexed-tree
4 / / 2 6 1 3 5 7
Let n = r - l + 1 where (l, r) is the range of the Fenwick tree. The complexities assume (<>) takes O(1) time.
Synopsis
- data FTree a
- emptyF :: Monoid a => (Int, Int) -> FTree a
- fromListF :: Monoid a => (Int, Int) -> [a] -> FTree a
- mappendF :: Commutative a => Int -> a -> FTree a -> FTree a
- foldPrefixF :: Monoid a => Int -> FTree a -> a
- foldRangeF :: (Commutative a, Group a) => Int -> Int -> FTree a -> a
- mappendRangeF :: (Commutative a, Group a) => Int -> Int -> a -> FTree a -> FTree a
- binSearchF :: Monoid a => (a -> Bool) -> FTree a -> Maybe (Int, a)
- toScanl1F :: Monoid a => FTree a -> [a]
Documentation
emptyF :: Monoid a => (Int, Int) -> FTree a Source #
Builds a Fenwick tree on range (l, r) where each element is mempty. O(log n).
fromListF :: Monoid a => (Int, Int) -> [a] -> FTree a Source #
Builds a Fenwick tree on (l, r) where the elements are taken from a list. If the list is shorter than the range, the remaining elements are mempty. O(n).
mappendF :: Commutative a => Int -> a -> FTree a -> FTree a Source #
mappends to the element at an index. O(log n).
foldPrefixF :: Monoid a => Int -> FTree a -> a Source #
The result of folding the prefix upto the given index. Indices outside the tree range are allowed, it is assumed elements there are mempty. O(log n).
foldRangeF :: (Commutative a, Group a) => Int -> Int -> FTree a -> a Source #
Folds the elements in the range (l, r). O(log n).
mappendRangeF :: (Commutative a, Group a) => Int -> Int -> a -> FTree a -> FTree a Source #
mappends to all elements in the range (l, r). Can be used with foldPrefixF for point queries. O(log n).