[Rust] Generic Segment Tree

Revision en3, by satylogin, 2022-04-25 15:56:17

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://mirror.codeforces.com/contest/1557/problem/D
my solution (https://mirror.codeforces.com/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.

Tags rust, data structures, segment tree

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English satylogin 2022-04-25 15:56:17 431 Tiny change: '30) uses\n~~~~\nle' -> '30) uses\n\n~~~~\nle'
en2 English satylogin 2022-04-25 07:05:56 87
en1 English satylogin 2022-04-23 08:15:43 1121 Initial revision (published)