competitive/data_structure/
range_minimum_query.rs

1const BLOCK_SIZE: usize = 64;
2
3#[derive(Clone, Debug)]
4pub struct RangeMinimumQuery<T> {
5    data: Vec<T>,
6    suffix: Vec<T>,
7    prefix: Vec<T>,
8    table: Vec<T>,
9    blocks: usize,
10}
11
12impl<T> RangeMinimumQuery<T>
13where
14    T: Ord + Copy,
15{
16    pub fn new(data: Vec<T>) -> Self {
17        let n = data.len();
18        let blocks = n.div_ceil(BLOCK_SIZE);
19        if blocks == 0 {
20            return Self {
21                data,
22                suffix: vec![],
23                prefix: vec![],
24                table: vec![],
25                blocks,
26            };
27        }
28        let levels = usize::BITS as usize - blocks.leading_zeros() as usize;
29        let mut table = vec![data[0]; levels * blocks];
30        let mut prefix = Vec::with_capacity(n);
31        let mut minimum = data[0];
32        for (i, &value) in data.iter().enumerate() {
33            minimum = if i % BLOCK_SIZE == 0 {
34                value
35            } else {
36                minimum.min(value)
37            };
38            prefix.push(minimum);
39            if i % BLOCK_SIZE == BLOCK_SIZE - 1 || i + 1 == n {
40                table[i / BLOCK_SIZE] = minimum;
41            }
42        }
43        let mut suffix = data.clone();
44        for block in suffix.chunks_mut(BLOCK_SIZE) {
45            minimum = *block.last().unwrap();
46            for value in block.iter_mut().rev() {
47                minimum = minimum.min(*value);
48                *value = minimum;
49            }
50        }
51        for level in 1..levels {
52            let current = level * blocks;
53            let previous = current - blocks;
54            let half = 1 << (level - 1);
55            for i in 0..blocks - (1 << level) + 1 {
56                table[current + i] = if table[previous + i] < table[previous + i + half] {
57                    table[previous + i]
58                } else {
59                    table[previous + i + half]
60                };
61            }
62        }
63
64        Self {
65            data,
66            suffix,
67            prefix,
68            table,
69            blocks,
70        }
71    }
72
73    #[inline]
74    pub fn fold(&self, l: usize, r: usize) -> T {
75        let r = r - 1;
76        let left_block = l / BLOCK_SIZE;
77        let right_block = r / BLOCK_SIZE;
78        if left_block + 1 < right_block {
79            let middle_blocks = right_block - left_block - 1;
80            let level = middle_blocks.ilog2() as usize;
81            let offset = level * self.blocks;
82            self.suffix[l]
83                .min(self.prefix[r])
84                .min(self.table[offset + left_block + 1])
85                .min(self.table[offset + right_block - (1 << level)])
86        } else if left_block < right_block {
87            self.suffix[l].min(self.prefix[r])
88        } else {
89            *self.data[l..=r].iter().min().unwrap()
90        }
91    }
92}
93
94#[cfg(test)]
95mod tests {
96    use super::*;
97    use crate::{
98        rand,
99        tools::{NotEmptySegment as Nes, Xorshift},
100    };
101
102    #[test]
103    fn test_range_minimum_query() {
104        let mut rng = Xorshift::default();
105        for _ in 0..100 {
106            rand!(rng, n: 1..200, arr: [-1000i64..=1000; n]);
107            let rmq = RangeMinimumQuery::new(arr.clone());
108            for _ in 0..200 {
109                rand!(rng, (l, r): Nes(n));
110                let expected = arr[l..r].iter().min().cloned().unwrap();
111                assert_eq!(rmq.fold(l, r), expected);
112            }
113        }
114    }
115}
competitive/data_structure/range_minimum_query.rs

competitive/data_structure/
range_minimum_query.rs
