binary-indexed-tree: Binary Indexed Trees (a.k.a. Fenwick Trees).
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).
Downloads
- binary-indexed-tree-0.1.tar.gz [browse] (Cabal source package)
- Package description (as included in the package)
Maintainer's Corner
For package maintainers and hackage trustees
Candidates
- No Candidates
Versions [RSS] | 0.1 |
---|---|
Dependencies | array (>=0.3), base (>=3 && <5) [details] |
License | LicenseRef-LGPL |
Author | Maxwell Sayles <maxwellsayles@gmail.com> |
Maintainer | Maxwell Sayles <maxwellsayles@gmail.com> |
Category | Data |
Uploaded | by MaxwellSayles at 2012-10-10T21:19:48Z |
Distributions | |
Reverse Dependencies | 1 direct, 0 indirect [details] |
Downloads | 1363 total (0 in the last 30 days) |
Rating | (no votes yet) [estimated by Bayesian average] |
Your Rating | |
Status | Docs uploaded by user Build status unknown [no reports yet] |