Crate seg_lib 

seg_lib provides segment tree variants.

Examples

use seg_lib::{SegmentTree, ops::Add};

/// Demonstrates how to use a [`SegmentTree`] for:
/// - range sum queries
/// - point updates (direct or functional)
fn main() {
    // Initialize a segment tree with 7 elements, all set to 0
    let mut seg = SegmentTree::<Add<i32>>::new(7);
    assert_eq!(seg.len(), 7);
    assert!(seg.iter().all(|e| *e == 0));

    // Update a single element
    seg.point_update(0, 100);
    assert_eq!(Vec::from_iter(seg.iter().copied()), vec![100, 0, 0, 0, 0, 0, 0]);

    // Query a single element and the sum over the entire range
    assert_eq!(seg.point_query(0), &100);
    assert_eq!(seg.range_query(..), 100);

    // Update a single element with a custom function
    seg.point_update_with(0, |x| x * 2 + 7);
    assert_eq!(Vec::from_iter(seg.iter().copied()), vec![207, 0, 0, 0, 0, 0, 0]);
}

See more examples.

Guide

	range query	range update	note
SegmentTree	✅	❌
DynamicSegmentTree	✅	❌	large array
DualSegmentTree	❌	✅
LazySegmentTree	✅	✅
DynamicLazySegmentTree	✅	✅	large array
AssignSegmentTree	✅	✅	specialized for range assign update

Modules

acts

Predefined monoid actions.

ops

Predefined operations on segment tree variants.

Structs

AssignSegmentTree

A data structure that supports range query range assign operations.

DualSegmentTree

A data structure that supports point query range update operations.

DynamicLazySegmentTree

A data structure that supports range query range update operations on large array.

DynamicSegmentTree

A data structure that supports range query point update operations on large array.

LazySegmentTree

A data structure that supports range query range update operations.

SegmentTree

A data structure that supports range query point update operations.

Traits

Monoid

A monoid is a set equipped with an associative binary operation and an identity element.

MonoidAction

A monoid action is a function *: M x S -> S of a monoid M on a monoid S.

QuasiMonoidAction

A function that behaves like a monoid action under well-defined conditions, which frequently hold in practice.