| Safe Haskell | None |
|---|---|
| Language | Haskell2010 |
FenwickMut
Description
Mutable Fenwick tree, or binary indexed tree
A data structure supporting point updates and range queries, or the opposite. See Fenwick.hs for a purely functional version. FenwickMut is multiple times faster when used with unboxed arrays (see benchmarks).
Sources:
- 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://en.wikipedia.org/wiki/Fenwick_tree
Let n = r - l + 1 where (l, r) is the range of the Fenwick tree. The complexities assume (<>) takes O(1) time.
Synopsis
- type FenwickMut marr a = marr Int a
- emptyFM :: (Monoid a, MArray marr a m) => (Int, Int) -> m (FenwickMut marr a)
- mappendFM :: (Monoid a, MArray marr a m) => FenwickMut marr a -> Int -> a -> m ()
- foldPrefixFM :: (Monoid a, MArray marr a m) => FenwickMut marr a -> Int -> m a
- foldRangeFM :: (Commutative a, Group a, MArray marr a m) => FenwickMut marr a -> Int -> Int -> m a
- mappendRangeFM :: (Commutative a, Group a, MArray marr a m) => FenwickMut marr a -> Int -> Int -> a -> m ()
Documentation
type FenwickMut marr a = marr Int a Source #
emptyFM :: (Monoid a, MArray marr a m) => (Int, Int) -> m (FenwickMut marr a) Source #
Builds a Fenwick tree on range (l, r) where each element is mempty. O(n).
mappendFM :: (Monoid a, MArray marr a m) => FenwickMut marr a -> Int -> a -> m () Source #
mappends to the element at an index. O(log n).
foldPrefixFM :: (Monoid a, MArray marr a m) => FenwickMut marr a -> Int -> m 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).
foldRangeFM :: (Commutative a, Group a, MArray marr a m) => FenwickMut marr a -> Int -> Int -> m a Source #
Folds the elements in the range (l, r). O(log n).
mappendRangeFM :: (Commutative a, Group a, MArray marr a m) => FenwickMut marr a -> Int -> Int -> a -> m () Source #
mappends to all elements in the range (l, r). Can be used with foldPrefixFM for point queries. O(log n).