Struct Rsq

pub struct Rsq<T: Default + Clone + Copy + Add<Output = T>> { /* private fields */ }

Range Sum Query

Implementations

impl<T> Rsq<T>

where T: Default + Clone + Copy + Add<Output = T>,

pub fn new(src: &[T]) -> Self

Build Segment Tree (RSQ) from slice.

 use librualg::segment_tree::Rsq;

 let arr = [1, 2, 3, 4, 5];
 let tree = Rsq::new(&arr);

pub fn query(&self, l: usize, r: usize) -> Option<T>

Returns the sum on the interval l to r

 use librualg::segment_tree::Rsq;

 let arr = [1, 2, 3, 4, 5];
 let tree = Rsq::new(&arr);

 assert_eq!(tree.query(0, 4).unwrap(), 15);
 assert_eq!(tree.query(1, 4).unwrap(), 14);
 assert_eq!(tree.query(4, 1).unwrap(), 14);
 assert_eq!(tree.query(3, 1).unwrap(), 9);
 assert_eq!(tree.query(3, 11), None);

pub fn update(&mut self, idx: usize, value: T)

Update value by index

 use librualg::segment_tree::Rsq;
 let arr = [1, 2, 3, 4, 5];
 let mut tree = Rsq::new(&arr);

 assert_eq!(tree.query(0, 4).unwrap(), 15);
 tree.update(1, 7);
 assert_eq!(tree.query(0, 4).unwrap(), 20);