Skip to main content

Crate segfen

Crate segfen 

Source
Expand description

§segfen

Range-query data structures for Rust: a SegmentTree generic over any user-defined Monoid, and a FenwickTree (binary indexed tree) for prefix sums. Both give O(log n) point updates and range queries.

Unlike ad-hoc implementations scattered across crates.io, the segment tree here is generic over the operation: sum, min, max, gcd, bitwise-or, matrix product — anything associative with an identity.

use segfen::{SegmentTree, Monoid, FenwickTree};

// Range-minimum query via a custom monoid.
struct Min;
impl Monoid for Min {
    type T = i64;
    fn identity() -> i64 { i64::MAX }
    fn combine(a: &i64, b: &i64) -> i64 { *a.min(b) }
}

let mut st = SegmentTree::<Min>::from_slice(&[5, 2, 8, 1, 9]);
assert_eq!(st.query(0..5), 1);
assert_eq!(st.query(0..3), 2);
st.update(3, 100);
assert_eq!(st.query(2..5), 8);

// Prefix sums via a Fenwick tree.
let mut fw = FenwickTree::from_slice(&[1i64, 2, 3, 4]);
assert_eq!(fw.range_sum(1..3), 5);
fw.add(0, 10);
assert_eq!(fw.prefix_sum(1), 11);

§Choosing a structure

SegmentTreeFenwickTree
Operationany Monoidaddition only
Queryarbitrary rangeprefix / range sum
Updateassign (update)add delta (add)
Memory2n elementsn + 1 elements

Prefer FenwickTree when you only need sums — it is smaller and has a tighter constant factor. Use SegmentTree for anything else.

§Complexity

Construction from a slice is O(n); every query and update is O(log n). SegmentTree::get is O(1).

§Panics

Index and range arguments are bounds-checked and panic on violation; see the individual methods. Empty ranges are valid and yield the monoid identity.

§Feature flags

  • std (enabled by default) — links against std. Disable it for no_std targets; the crate then needs only alloc:
segfen = { version = "0.1", default-features = false }

Structs§

FenwickTree
A Fenwick tree (binary indexed tree) for O(log n) prefix sums and point additions over an additive type.
SegmentTree
An iterative segment tree supporting point update and range query in O(log n), generic over a Monoid.
Sum
Ready-made sum monoid for any numeric-like type.

Traits§

Monoid
An associative operation with an identity element.