Crate seg_lib 

seg_lib provides segment tree variants.

Example

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

// point update range sum query
let mut seg_tree = SegmentTree::<Add<i32>>::from_iter(0..1_000);

assert_eq!(seg_tree.range_query(..), 999 * 1_000 / 2);

// replace 0-th element with 100
seg_tree.point_update(0, 100);
assert_eq!(seg_tree.point_query(0), &100);

// twice 10-th element
seg_tree.point_update_with(10, |v| v * 2);
assert_eq!(seg_tree.point_query(10), &20);
assert_eq!(seg_tree.range_query(..), 999 * 1_000 / 2 + 110)

See more examples.

Guide

	range query	range update	comments
SegmentTree	✅	❌
DualSegmentTree	❌	✅
LazySegmentTree	✅	✅
AssignSegmentTree	✅	✅	specialized for range assign update
SegmentTreeBeats	✅	✅	UNDER CONSTRUCTION

Modules

ops

Predefined operations on segment tree variants.

traits

Traits that abstracts the algebra that can be applied over a 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.

LazySegmentTree

A data structure that supports range query range update operations.

SegmentTree

A data structure that supports range query point update operations.

SegmentTreeBeats

UNDER CONSTRUCTION