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
SegmentTree | FenwickTree | |
|---|---|---|
| Operation | any Monoid | addition only |
| Query | arbitrary range | prefix / range sum |
| Update | assign (update) | add delta (add) |
| Memory | 2n elements | n + 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 againststd. Disable it forno_stdtargets; the crate then needs onlyalloc:
segfen = { version = "0.1", default-features = false }Structs§
- Fenwick
Tree - A Fenwick tree (binary indexed tree) for
O(log n)prefix sums and point additions over an additive type. - Segment
Tree - An iterative segment tree supporting point update and range query in
O(log n), generic over aMonoid. - Sum
- Ready-made sum monoid for any numeric-like type.
Traits§
- Monoid
- An associative operation with an identity element.