# The binary-indexed-tree package

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).

## Properties

Version | 0.1 |
---|---|

Change log | None available |

Dependencies | array (>=0.3), base (>=3 && <5) |

License | LGPL |

Author | Maxwell Sayles <maxwellsayles@gmail.com> |

Maintainer | Maxwell Sayles <maxwellsayles@gmail.com> |

Stability | Stable |

Category | Data |

Uploaded | Wed Oct 10 21:19:48 UTC 2012 by MaxwellSayles |

Distributions | NixOS:0.1 |

Downloads | 263 total (16 in last 30 days) |

Status | Docs uploaded by user Build status unknown [no reports yet] |

## Modules

[Index]

## Downloads

- binary-indexed-tree-0.1.tar.gz [browse] (Cabal source package)
- Package description (included in the package)

#### Maintainers' corner

For package maintainers and hackage trustees