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.
The major benefit is that it allows for me to write more complicated segtree rather easily,
eg:
for problem: https://codeforces.net/contest/1557/problem/D
my solution (https://codeforces.net/contest/1557/submission/154901530) uses
let mut seg_tree = SegTree::new(
points.len(),
(0, 0),
|left: (usize, usize), right: (usize, usize)| if left.1 > right.1 { left } else { right },
);
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.
