segfen
Range-query data structures for Rust:
SegmentTree<M>— an iterative segment tree generic over any user-defined monoid: sum, min, max, gcd, bitwise-or, matrix product — anything associative with an identity.FenwickTree<T>— a Fenwick tree (binary indexed tree) for prefix sums and point additions over an additive type.
Both provide O(log n) point updates and range queries, with O(n) construction
from a slice. No dependencies, no unsafe, no_std compatible.
Installation
[]
= "0.1"
Or:
Quick start
use ;
// Range-minimum query via a custom monoid.
;
let mut st = from_slice;
assert_eq!;
assert_eq!;
st.update;
assert_eq!;
// Prefix sums via a Fenwick tree.
let mut fw = from_slice;
assert_eq!;
fw.add;
assert_eq!;
Defining a monoid
Implement the Monoid trait for a marker type. The implementation must uphold
two laws:
- Identity —
combine(identity(), x) == x == combine(x, identity()) - Associativity —
combine(combine(a, b), c) == combine(a, combine(b, c))
use ;
;
let st = from_slice;
assert_eq!;
assert_eq!;
A ready-made Sum monoid is provided for any type implementing
Clone + Default + Add:
use ;
let st = from_slice;
assert_eq!;
Choosing between the two
SegmentTree<M> |
FenwickTree<T> |
|
|---|---|---|
| Operation | any monoid | addition only |
| Query | arbitrary range | prefix / range sum |
| Update | assign (update) |
add delta (add) |
| Memory | 2n elements |
n + 1 elements |
| Requires | Monoid impl |
Clone + Default + AddAssign + Sub |
Use FenwickTree when you only need sums — it is smaller and has a tighter
constant factor. Use SegmentTree for anything else.
Complexity
| Operation | SegmentTree |
FenwickTree |
|---|---|---|
from_slice |
O(n) |
O(n) |
new |
O(n) |
O(n) |
query / range_sum |
O(log n) |
O(log n) |
update / add |
O(log n) |
O(log n) |
get |
O(1) |
— |
no_std
The crate is no_std compatible and requires only alloc. Disable the default
std feature:
[]
= { = "0.1", = false }
Panics
Index and range arguments are checked. Methods panic on out-of-bounds access — see the per-method documentation on docs.rs. Empty ranges are valid and yield the monoid identity.
Minimum supported Rust version
Rust 1.75. Raising the MSRV is considered a breaking change and will only
happen in a minor version bump while 0.x.
License
Licensed under either of
- Apache License, Version 2.0 (LICENSE-APACHE or https://www.apache.org/licenses/LICENSE-2.0)
- MIT license (LICENSE-MIT or https://opensource.org/licenses/MIT)
at your option.
Contribution
Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in the work by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any additional terms or conditions.