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>>::from_iter(0..10);
    assert_eq!(seg.len(), 10);
    // Iterates all elements in O(N) time
    assert_eq!(seg.iter().sum::<i32>(), (0 + 9) * 10 / 2);

    // Update a single element
    seg.point_update(0, 100);
    assert_eq!(
        Vec::from_iter(seg.iter().copied()),
        vec![100, 1, 2, 3, 4, 5, 6, 7, 8, 9]
    );

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

    // Update a single element with a custom function
    seg.point_update_with(5, |x| x * 2 + 7);
    assert_eq!(
        Vec::from_iter(seg.iter().copied()),
        vec![100, 1, 2, 3, 4, 17, 6, 7, 8, 9]
    );

    // Performs binary search in O(log N) time
    assert_eq!(seg.partition_end(0, |sum| *sum <= 120), 5);
    assert_eq!(seg.partition_start(8, |sum| *sum <= 100), 1);
}

See more examples.

Guide

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

Dynamic dual segment tree will no be implemented because it is useless.

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.