Binary Indexed Trees (a.k.a. Fenwick Trees).
|Latest on Hackage:||0.1|
This package is not currently in any snapshots. If you're interested in using it, we recommend adding it to Stackage Nightly. Doing so will make builds more reliable, and allow stackage.org to host generated Haddocks.
Binary indexed trees are a data structure on indexes 1 through n. They allow you to compute the sum of all values at indexes 1 through i in O(logn) and to increase the value at index i in O(logn).
This implements binary indexed trees, both as an immutable data structure in pure code and as a mutable data structure using the ST Monad.
Both the immutable and mutable version have the same runtime complexity, but the mutable version has a smaller constant.
Written by Maxwell Sayles (2012).