segfen 0.1.0

Generic segment tree (over any monoid) and Fenwick/binary-indexed tree for O(log n) range queries. no_std compatible.
Documentation
  • Coverage
  • 100%
    22 out of 22 items documented2 out of 21 items with examples
  • Size
  • Source code size: 34.0 kB This is the summed size of all the files inside the crates.io package for this release.
  • Documentation size: 268.5 kB This is the summed size of all files generated by rustdoc for all configured targets
  • Ø build duration
  • this release: 3s Average build duration of successful builds.
  • all releases: 3s Average build duration of successful builds in releases after 2024-10-23.
  • Links
  • Homepage
  • faizanali2k05/segfen
    12 0 0
  • crates.io
  • Dependencies
  • Versions
  • Owners
  • faizanali2k05

segfen

crates.io docs.rs license

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

[dependencies]
segfen = "0.1"

Or:

cargo add segfen

Quick start

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

// 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);

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 segfen::{Monoid, SegmentTree};

struct Gcd;
impl Monoid for Gcd {
    type T = u64;
    fn identity() -> u64 { 0 } // gcd(0, x) == x
    fn combine(a: &u64, b: &u64) -> u64 {
        let (mut a, mut b) = (*a, *b);
        while b != 0 {
            let t = a % b;
            a = b;
            b = t;
        }
        a
    }
}

let st = SegmentTree::<Gcd>::from_slice(&[12, 18, 24, 5]);
assert_eq!(st.query(0..3), 6);
assert_eq!(st.query(0..4), 1);

A ready-made Sum monoid is provided for any type implementing Clone + Default + Add:

use segfen::{Sum, SegmentTree};

let st = SegmentTree::<Sum<i64>>::from_slice(&[1, 2, 3, 4, 5]);
assert_eq!(st.query(1..4), 9);

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:

[dependencies]
segfen = { version = "0.1", default-features = 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

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.