DEV Community

Satyarth Agrahari
Satyarth Agrahari

Posted on • Updated on

[Rust] Generic Segment Tree

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>
    T: Clone + Copy,
    F: Fn(T, T) -> T,
    n: i32,
    default: T,
    cell: Vec<T>,
    lazy: Vec<T>,
    op: F,
Enter fullscreen mode Exit fullscreen mode

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);
Enter fullscreen mode Exit fullscreen mode

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,
for problem:
my solution ( uses

let mut seg_tree = SegTree::new(
    (0, 0),
    |left: (usize, usize), right: (usize, usize)| if left.1 > right.1 { left } else { right },
Enter fullscreen mode Exit fullscreen mode

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.

Top comments (0)