binary-indexed-tree: Binary Indexed Trees (a.k.a. Fenwick Trees).

[ data, library ] [ Propose Tags ] [ Report a vulnerability ]

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

Maintainer's Corner

Package maintainers

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]