#prefix #tree #sum #fenwick #no-std

no-std ftree

A very fast fenwick tree implementation

5 releases (3 stable)

1.1.0 May 24, 2024
1.0.1 Feb 17, 2024
1.0.0 Jul 14, 2023
0.1.1 Jul 13, 2023
0.1.0 Jul 12, 2023

#1115 in Data structures

Download history 68/week @ 2024-03-13 35/week @ 2024-03-20 26/week @ 2024-03-27 44/week @ 2024-04-03 56/week @ 2024-04-10 67/week @ 2024-04-17 28/week @ 2024-04-24 46/week @ 2024-05-01 40/week @ 2024-05-08 171/week @ 2024-05-15 203/week @ 2024-05-22 76/week @ 2024-05-29 47/week @ 2024-06-05 95/week @ 2024-06-12 110/week @ 2024-06-19 51/week @ 2024-06-26

316 downloads per month
Used in 3 crates (2 directly)

Apache-2.0 OR MIT

12KB
168 lines

ftree

crates.io docs

A pure-rust(with zero dependencies, no-std) fenwick tree, for the efficient computation of dynamic prefix sums.

Background

Did you ever have to keep track of a sum, and update it at the same time?

Let's say that you have an array that represents the lengths of some other containers: [1, 6, 3, 9, 2]

What if you want to get the sum up until the n-th element? In the worst-case, this will take O(n) time. Updating on the other hand, is simply a matter of incrementing at the specified index, at O(1).

A fenwick tree allows you to both get the sum and do updates in O(log n) time.

Moreover, let's assume that you want to get the index of the first value such that <= sum.

Without using a Fenwick tree, this would take (n * log n) time (a binary search with the sum being computed during each iteration). Using one however, only takes O(log n) time. This might seem like a very niche need, and it is. It is utilized in the indexset crate, a two-level B-Tree, to very efficiently support vector-like indexing by position.

Performance

It's very performant. I have searched all over codeforces for all competitive programming fenwick tree performance tricks that there are, and put them all in this crate.

Naming

This library is called ftree, because the base data structure is FenwickTree.

Changelog

See CHANGELOG.md.

Dependencies

~175KB