[Rust] Generic Segment Tree

Правка en3, от 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.

Теги rust, data structures, segment tree

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский satylogin 2022-04-25 15:56:17 431 Tiny change: '30) uses\n~~~~\nle' -> '30) uses\n\n~~~~\nle'
en2 Английский satylogin 2022-04-25 07:05:56 87
en1 Английский satylogin 2022-04-23 08:15:43 1121 Initial revision (published)