Struct librualg::segment_tree::RmqMin

pub struct RmqMin<T: Default + Clone + Copy + SegmentTreeMin + SegmentTreeMax + Ord> { /* fields omitted */ }

Range Minimum Query

Implementations

impl<T> RmqMin<T> where
    T: Default + Clone + Copy + SegmentTreeMin + SegmentTreeMax + Ord, 

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

Build Segment Tree (RMQMin) from slice.

 use librualg::segment_tree::{RmqMin, SegmentTreeMin, SegmentTreeMax};
 use std::prelude::v1::*;

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

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

Returns the minimal on the interval l to r

 use librualg::segment_tree::{Rsq, RmqMin};

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

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

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

Update value by index

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

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