Struct RangeMinimumQuery 

pub struct RangeMinimumQuery<T> {
    data: Vec<T>,
    mask: Vec<u64>,
    sparse: Vec<usize>,
    sparse_offset: Vec<usize>,
}

Fields

data: Vec<T>

mask: Vec<u64>

sparse: Vec<usize>

sparse_offset: Vec<usize>

Implementations

impl<T> RangeMinimumQuery<T>

where T: Ord,

pub fn new(data: Vec<T>) -> Self

Examples found in repository

crates/library_checker/src/data_structure/staticrmq.rs (line 35)

pub fn staticrmq_range_minimum_query(reader: impl Read, mut writer: impl Write) {
    let s = read_all_unchecked(reader);
    let mut scanner = Scanner::new(&s);
    scan!(scanner, n, q, a: [u64; n], lr: [(usize, usize)]);
    let rmq = RangeMinimumQuery::new(a);
    for (l, r) in lr.take(q) {
        writeln!(writer, "{}", rmq.fold(l, r)).ok();
    }
}

crates/competitive/src/string/string_search.rs (line 74)

    pub fn new(text: Vec<T>) -> Self {
        let suffix_array = SuffixArray::new(&text);

        let (lcp_array, rank) = suffix_array.lcp_array_with_rank(&text);
        let rmq = RangeMinimumQuery::new(lcp_array.clone());

        Self {
            text,
            suffix_array,
            lcp_array,
            rank,
            rmq,
        }
    }

crates/competitive/src/tree/euler_tour.rs (line 199)

    pub fn lca(&self, root: usize) -> LowestCommonAncestor {
        let depth = self.tree_depth(root);
        let mut trace = Vec::with_capacity(2 * self.vertices_size() - 1);
        let mut depth_trace = Vec::with_capacity(2 * self.vertices_size() - 1);
        let euler_tour = self.full_euler_tour_builder(root).build_with_trace(|u| {
            trace.push(u);
            depth_trace.push(depth[u]);
        });
        let rmq = RangeMinimumQuery::new(depth_trace);
        LowestCommonAncestor {
            euler_tour,
            trace,
            rmq,
        }
    }

pub fn len(&self) -> usize

pub fn is_empty(&self) -> bool

pub fn get(&self, index: usize) -> &T

fn min_index(&self, a: usize, b: usize) -> usize

Examples found in repository

crates/competitive/src/data_structure/range_minimum_query.rs (line 113)

    fn argmin_blocks(&self, l_block: usize, r_block: usize) -> usize {
        debug_assert!(l_block < r_block);
        let len = r_block - l_block;
        let k = len.ilog2() as usize;
        let offset = self.sparse_offset[k];
        let left = self.sparse[offset + l_block];
        let right = self.sparse[offset + r_block - (1usize << k)];
        self.min_index(left, right)
    }

    pub fn argmin(&self, l: usize, r: usize) -> usize {
        assert!(l < r);
        assert!(r <= self.data.len());
        let r = r - 1;
        let bl = l >> BLOCK_SHIFT;
        let br = r >> BLOCK_SHIFT;
        if bl == br {
            return self.argmin_in_block(l, r);
        }
        let left_end = ((bl + 1) << BLOCK_SHIFT) - 1;
        let right_start = br << BLOCK_SHIFT;
        let mut best = self.min_index(
            self.argmin_in_block(l, left_end),
            self.argmin_in_block(right_start, r),
        );
        if bl + 1 < br {
            let mid = self.argmin_blocks(bl + 1, br);
            best = self.min_index(best, mid);
        }
        best
    }

fn argmin_in_block(&self, l: usize, r: usize) -> usize

Examples found in repository

crates/competitive/src/data_structure/range_minimum_query.rs (line 123)

    pub fn argmin(&self, l: usize, r: usize) -> usize {
        assert!(l < r);
        assert!(r <= self.data.len());
        let r = r - 1;
        let bl = l >> BLOCK_SHIFT;
        let br = r >> BLOCK_SHIFT;
        if bl == br {
            return self.argmin_in_block(l, r);
        }
        let left_end = ((bl + 1) << BLOCK_SHIFT) - 1;
        let right_start = br << BLOCK_SHIFT;
        let mut best = self.min_index(
            self.argmin_in_block(l, left_end),
            self.argmin_in_block(right_start, r),
        );
        if bl + 1 < br {
            let mid = self.argmin_blocks(bl + 1, br);
            best = self.min_index(best, mid);
        }
        best
    }

fn argmin_blocks(&self, l_block: usize, r_block: usize) -> usize

Examples found in repository

crates/competitive/src/data_structure/range_minimum_query.rs (line 132)

    pub fn argmin(&self, l: usize, r: usize) -> usize {
        assert!(l < r);
        assert!(r <= self.data.len());
        let r = r - 1;
        let bl = l >> BLOCK_SHIFT;
        let br = r >> BLOCK_SHIFT;
        if bl == br {
            return self.argmin_in_block(l, r);
        }
        let left_end = ((bl + 1) << BLOCK_SHIFT) - 1;
        let right_start = br << BLOCK_SHIFT;
        let mut best = self.min_index(
            self.argmin_in_block(l, left_end),
            self.argmin_in_block(right_start, r),
        );
        if bl + 1 < br {
            let mid = self.argmin_blocks(bl + 1, br);
            best = self.min_index(best, mid);
        }
        best
    }

pub fn argmin(&self, l: usize, r: usize) -> usize

Examples found in repository

crates/competitive/src/data_structure/range_minimum_query.rs (line 144)

    pub fn fold(&self, l: usize, r: usize) -> T {
        let idx = self.argmin(l, r);
        self.data[idx].clone()
    }

crates/competitive/src/tree/euler_tour.rs (line 262)

    pub fn lca(&self, u: usize, v: usize) -> usize {
        let mut l = self.euler_tour.vidx[u][0];
        let mut r = self.euler_tour.vidx[v][0];
        if l > r {
            swap(&mut l, &mut r);
        }
        let idx = self.rmq.argmin(l, r + 1);
        self.trace[idx]
    }

impl<T> RangeMinimumQuery<T>

where T: Ord + Clone,

pub fn fold(&self, l: usize, r: usize) -> T

Examples found in repository

crates/competitive/src/string/string_search.rs (line 146)

    fn lcp_sa(&self, a: usize, b: usize) -> usize {
        if a == b {
            return self.text.len() - self.suffix_array[a];
        }
        let (l, r) = if a < b { (a, b) } else { (b, a) };
        self.rmq.fold(l, r)
    }

crates/library_checker/src/data_structure/staticrmq.rs (line 37)

pub fn staticrmq_range_minimum_query(reader: impl Read, mut writer: impl Write) {
    let s = read_all_unchecked(reader);
    let mut scanner = Scanner::new(&s);
    scan!(scanner, n, q, a: [u64; n], lr: [(usize, usize)]);
    let rmq = RangeMinimumQuery::new(a);
    for (l, r) in lr.take(q) {
        writeln!(writer, "{}", rmq.fold(l, r)).ok();
    }
}

Trait Implementations

impl<T: Clone> Clone for RangeMinimumQuery<T>

fn clone(&self) -> RangeMinimumQuery<T>

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<T: Debug> Debug for RangeMinimumQuery<T>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.