competitive::data_structure::disjoint_sparse_table

Struct DisjointSparseTable

pub struct DisjointSparseTable<S>where
    S: SemiGroup,{
    table: Vec<S::T>,
    offsets: Vec<usize>,
    len: usize,
}

Fields§

§table: Vec<S::T>§offsets: Vec<usize>§len: usize

Implementations§

Source §

impl<S> DisjointSparseTable<S>
where S: SemiGroup,

Source

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

Examples found in repository ?

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

8pub fn staticrmq_disjoint_sparse_table(reader: impl Read, writer: impl Write) {
9    prepare_io!(reader, writer);
10    sc!(n, q, a: [u64; n], lr: [(usize, usize); iter q]);
11    let table = DisjointSparseTable::<MinOperation<_>>::new(a);
12    for (l, r) in lr {
13        pp!(table.fold(l, r));
14    }
15}

More examples

Hide additional examples

crates/competitive/src/data_structure/static_range_product.rs (line 167)

160    fn new(data: Vec<S::T>, level: usize) -> Self {
161        let n = data.len();
162        if n <= DIRECT_SIZE || level == 0 {
163            return Self::Direct { data };
164        }
165        if level == 1 {
166            return Self::Disjoint {
167                table: DisjointSparseTable::new(data),
168            };
169        }
170        let block_shift = scaled_block_shift(alpha_k(level - 1, n));
171        let block_size = 1usize << block_shift;
172        if block_size <= 1 || block_size >= n {
173            return Self::Direct { data };
174        }
175        let blocks = block_products::<S>(&data, block_size);
176        let between = Box::new(Self::new(blocks.products, level - 1));
177        Self::Recursive {
178            data,
179            block_shift,
180            prefix: blocks.prefix,
181            suffix: blocks.suffix,
182            between,
183        }
184    }

Source

pub fn height(&self) -> usize

Examples found in repository ?

crates/competitive/src/data_structure/disjoint_sparse_table.rs (line 94)

93    pub fn fold_close(&self, l: usize, r: usize) -> S::T {
94        debug_assert!(l < self.height());
95        debug_assert!(r < self.height());
96        debug_assert!(l <= r);
97        if let Some(x) = Self::most_significant_bit_place(l ^ r) {
98            let offset = self.offsets[x];
99            S::operate(&self.table[offset + l], &self.table[offset + r])
100        } else {
101            self.table[l].clone()
102        }
103    }

Source

fn most_significant_bit_place(x: usize) -> Option<usize>

Examples found in repository ?

crates/competitive/src/data_structure/disjoint_sparse_table.rs (line 97)

93    pub fn fold_close(&self, l: usize, r: usize) -> S::T {
94        debug_assert!(l < self.height());
95        debug_assert!(r < self.height());
96        debug_assert!(l <= r);
97        if let Some(x) = Self::most_significant_bit_place(l ^ r) {
98            let offset = self.offsets[x];
99            S::operate(&self.table[offset + l], &self.table[offset + r])
100        } else {
101            self.table[l].clone()
102        }
103    }

Source

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

Examples found in repository ?

crates/competitive/src/data_structure/disjoint_sparse_table.rs (line 107)

105    pub fn fold(&self, l: usize, r: usize) -> S::T {
106        debug_assert!(l < r);
107        self.fold_close(l, r - 1)
108    }

Source

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

Examples found in repository ?

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

8pub fn staticrmq_disjoint_sparse_table(reader: impl Read, writer: impl Write) {
9    prepare_io!(reader, writer);
10    sc!(n, q, a: [u64; n], lr: [(usize, usize); iter q]);
11    let table = DisjointSparseTable::<MinOperation<_>>::new(a);
12    for (l, r) in lr {
13        pp!(table.fold(l, r));
14    }
15}

More examples

Hide additional examples

crates/competitive/src/data_structure/static_range_product.rs (line 190)

187    fn fold(&self, l: usize, r: usize) -> S::T {
188        match self {
189            Self::Direct { data } => fold_slice::<S>(data, l, r),
190            Self::Disjoint { table } => table.fold(l, r),
191            Self::Recursive {
192                data,
193                block_shift,
194                prefix,
195                suffix,
196                between,
197            } => {
198                let block_shift = *block_shift;
199                let bl = l >> block_shift;
200                let br = (r - 1) >> block_shift;
201                if bl == br {
202                    return fold_slice::<S>(data, l, r);
203                }
204                let mut res = suffix[l].clone();
205                if bl + 1 < br {
206                    let mid = between.fold(bl + 1, br);
207                    res = S::operate(&res, &mid);
208                }
209                S::operate(&res, &prefix[r - 1])
210            }
211        }
212    }