Prefix sum tree over B-Tree Map

help
1

Does anyone know of an implementation of a prefix sum tree over a B-Tree Map? Or if I can use BTreeMap to do it? For 2-ary version of this, see Fenwick Tree

Perhaps I am just too unfamiliar with the BTreeMap API, but I'd need to modify values from nodes mid-traversal and I'm unsure if I can do that. This would work if I could access inner or outer nodes, I'd just define the partial sum value a little differently depending on which level of node.

2 
fn prefix_sum(map: &mut BTreeMap<String, i32>) -> i32 {
    map.iter_mut().fold(0, |acc, (_, v)| { *v += acc; *v })
}
3

Oh whoops, I was careless with my wording. I'm looking at what nodes would need to hold and modify in the data structure to behave like a prefix sum tree, for binary search tree prefix sums, we have the Fenwick Tree, and I wish to generalize that notion to a k-ary tree.

I'm expecting that insertion operations would need to update node properties during traversal, and this could get tricky with node splitting. I'll modify the question as well.

4

You can't do that with the BTreeMap from the stdlib, but a general BTrees can support it if you augment it by storing in each node the sum of the elements in the subtree rooted in that node.

3 Likes
6

Oh, well I may have to do real work lol.

I couldn't find any pre-existing augmentable B-Tree Map crates (sets of traits with a few provided methods and perhaps a few implementations), would you happen to know of one? Or perhaps I've found an opportunity for a little crate.

7

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.