seqan/seqan — pull request #343 by rrahn (2014-05-14 21:25:10+00:00)
Title: Feature/dps

Initial commit of a dynamic data structure that can compute a prefix sum and supports insert/delete in O(b log_b(n)) time, where b is the branching factor of the underlying B-Tree implementation. The prefix sum can be computed in O(log(b)*log_b(n)) time by traversing the tree beginning in the root.
At the moment only insert is implemented. Delete should be straight forward but is not needed yet.
This commit includes tests for the new data structure.
Documentation will be added soon.