Struct RmqMax

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

Range Maximum Query

Implementations

impl<T> RmqMax<T>

where T: Default + Clone + Copy + SegmentTreeMin + SegmentTreeMax + Ord,

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

Build Segment Tree (RMQMax) from slice.

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

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

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

Returns the maximum on the interval l to r

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

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

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

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

Update value by index

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

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