I wanted to write and keep a segment tree implementation for myself, that I could use more generally (all reasonable data types, and all reasonable operations). I finally decided to write one and add it to cp-lib.
The core struct for now is:
pub struct SegTree<T, F>
where
T: Clone + Copy,
F: Fn(T, T) -> T,
{
n: i32,
default: T,
cell: Vec<T>,
lazy: Vec<T>,
op: F,
}
And usage:
let mut tree = SegTree::new(10, i32::MIN, std::cmp::max);
tree.insert(1, 10);
tree.insert(2, 20);
assert_eq!(tree.query(1, 10), 20);
tree.insert_range(3, 6, 10);
assert_eq!(tree.query(5, 10), 10);
Where op is the operation that the segment tree performs (min, max, gcd, or something custom), and default is the value the should be returned as query default and gets stored during initialization.
Sharing the full implementation here in case someone needs it.
I will keep on modifying it as needed. In case anyone do decide to use it and find some bugs, or have a feature request, do let me know.