Struct WaveletMatrixFold 

pub struct WaveletMatrixFold<'a, T, M>
where
    T: Ord + Clone,
    M: AbelianGroup,
{
    wavelet_matrix: &'a WaveletMatrix<T>,
    prefix: Vec<M::T>,
    offsets: Vec<usize>,
}

Fields

wavelet_matrix: &'a WaveletMatrix<T>

prefix: Vec<M::T>

offsets: Vec<usize>

Implementations

impl<'a, T, M> WaveletMatrixFold<'a, T, M>

where T: Ord + Clone, M: AbelianGroup,

pub fn fold_lessthan(&self, val: T, range: Range<usize>) -> M::T

pub fn fold_lessthan_with_count( &self, val: T, range: Range<usize>, ) -> (usize, M::T)

Examples found in repository

crates/competitive/src/data_structure/wavelet_matrix.rs (line 1590)

    pub fn fold_lessthan(&self, val: T, range: Range<usize>) -> M::T {
        self.fold_lessthan_with_count(val, range).1
    }

crates/library_checker/src/data_structure/static_range_sum_with_upper_bound.rs (line 30)

pub fn static_range_sum_with_upper_bound_wavelet_matrix(reader: impl Read, writer: impl Write) {
    prepare_io!(reader, writer);
    sc!(n, q, a: [i64; n]);
    let weights = a.clone();
    let wm = WaveletMatrix::new(a);
    let fold = wm.build_fold::<AdditiveOperation<i64>>(&weights);
    for _ in 0..q {
        sc!(l, r, x: i64);
        let (count, sum) = fold.fold_lessthan_with_count(x + 1, l..r);
        pp!(count, sum);
    }
}

pub fn fold_range(&self, valrange: Range<T>, range: Range<usize>) -> M::T

pub fn fold_range_with_count( &self, valrange: Range<T>, range: Range<usize>, ) -> (usize, M::T)

Examples found in repository

crates/competitive/src/data_structure/wavelet_matrix.rs (line 1604)

    pub fn fold_range(&self, valrange: Range<T>, range: Range<usize>) -> M::T {
        self.fold_range_with_count(valrange, range).1
    }

fn range_sum(&self, level: usize, range: Range<usize>) -> M::T

Examples found in repository

crates/competitive/src/data_structure/wavelet_matrix.rs (line 1648)

    pub fn fold_range_with_count(
        &self,
        valrange: Range<T>,
        mut range: Range<usize>,
    ) -> (usize, M::T) {
        debug_assert!(range.end <= self.wavelet_matrix.len);
        let lower = self
            .wavelet_matrix
            .compress
            .index_lower_bound(&valrange.start);
        let upper = self
            .wavelet_matrix
            .compress
            .index_lower_bound(&valrange.end);
        if lower >= upper {
            return (0, M::unit());
        }
        for d in (0..self.wavelet_matrix.bit_length).rev() {
            let level = self.wavelet_matrix.level(d);
            let start1 = self.wavelet_matrix.bit_vectors[level].rank1(range.start);
            let end1 = self.wavelet_matrix.bit_vectors[level].rank1(range.end);
            let start0 = range.start - start1;
            let end0 = range.end - end1;
            if ((lower >> d) & 1) == ((upper >> d) & 1) {
                if ((lower >> d) & 1) == 0 {
                    range = start0..end0;
                } else {
                    range = self.wavelet_matrix.zeros[level] + start1
                        ..self.wavelet_matrix.zeros[level] + end1;
                }
                continue;
            }
            let zero_range = start0..end0;
            let one_range =
                self.wavelet_matrix.zeros[level] + start1..self.wavelet_matrix.zeros[level] + end1;
            let [(lower_count, lower_sum), (upper_count, upper_sum)] = self
                .fold_lessthan_indices_with_count(
                    [lower, upper],
                    [zero_range.clone(), one_range],
                    d,
                );
            let zero_sum = self.range_sum(level, zero_range.clone());
            return (
                zero_range.len() - lower_count + upper_count,
                M::operate(&M::rinv_operate(&zero_sum, &lower_sum), &upper_sum),
            );
        }
        (0, M::unit())
    }

    #[inline]
    fn range_sum(&self, level: usize, range: Range<usize>) -> M::T {
        let offset = self.offsets[level];
        M::rinv_operate(
            &self.prefix[offset + range.end],
            &self.prefix[offset + range.start],
        )
    }

    fn fold_lessthan_indices_with_count<const N: usize>(
        &self,
        indices: [usize; N],
        mut ranges: [Range<usize>; N],
        bits: usize,
    ) -> [(usize, M::T); N] {
        let mut results = std::array::from_fn(|_| (0, M::unit()));
        let last = indices
            .iter()
            .map(|index| index.trailing_zeros() as usize)
            .min()
            .unwrap_or(bits);
        for d in (last..bits).rev() {
            let level = self.wavelet_matrix.level(d);
            for ((&index, range), (count, sum)) in indices.iter().zip(&mut ranges).zip(&mut results)
            {
                let start1 = self.wavelet_matrix.bit_vectors[level].rank1(range.start);
                let end1 = self.wavelet_matrix.bit_vectors[level].rank1(range.end);
                let start0 = range.start - start1;
                let end0 = range.end - end1;
                if ((index >> d) & 1) != 0 {
                    *count += end0 - start0;
                    M::operate_assign(sum, &self.range_sum(level, start0..end0));
                    range.start = self.wavelet_matrix.zeros[level] + start1;
                    range.end = self.wavelet_matrix.zeros[level] + end1;
                } else {
                    range.start = start0;
                    range.end = end0;
                }
            }
        }
        results
    }

fn fold_lessthan_indices_with_count<const N: usize>( &self, indices: [usize; N], ranges: [Range<usize>; N], bits: usize, ) -> [(usize, M::T); N]

Examples found in repository

crates/competitive/src/data_structure/wavelet_matrix.rs (lines 1595-1599)

    pub fn fold_lessthan_with_count(&self, val: T, range: Range<usize>) -> (usize, M::T) {
        debug_assert!(range.end <= self.wavelet_matrix.len);
        let [result] = self.fold_lessthan_indices_with_count(
            [self.wavelet_matrix.compress.index_lower_bound(&val)],
            [range],
            self.wavelet_matrix.bit_length,
        );
        result
    }

    pub fn fold_range(&self, valrange: Range<T>, range: Range<usize>) -> M::T {
        self.fold_range_with_count(valrange, range).1
    }

    pub fn fold_range_with_count(
        &self,
        valrange: Range<T>,
        mut range: Range<usize>,
    ) -> (usize, M::T) {
        debug_assert!(range.end <= self.wavelet_matrix.len);
        let lower = self
            .wavelet_matrix
            .compress
            .index_lower_bound(&valrange.start);
        let upper = self
            .wavelet_matrix
            .compress
            .index_lower_bound(&valrange.end);
        if lower >= upper {
            return (0, M::unit());
        }
        for d in (0..self.wavelet_matrix.bit_length).rev() {
            let level = self.wavelet_matrix.level(d);
            let start1 = self.wavelet_matrix.bit_vectors[level].rank1(range.start);
            let end1 = self.wavelet_matrix.bit_vectors[level].rank1(range.end);
            let start0 = range.start - start1;
            let end0 = range.end - end1;
            if ((lower >> d) & 1) == ((upper >> d) & 1) {
                if ((lower >> d) & 1) == 0 {
                    range = start0..end0;
                } else {
                    range = self.wavelet_matrix.zeros[level] + start1
                        ..self.wavelet_matrix.zeros[level] + end1;
                }
                continue;
            }
            let zero_range = start0..end0;
            let one_range =
                self.wavelet_matrix.zeros[level] + start1..self.wavelet_matrix.zeros[level] + end1;
            let [(lower_count, lower_sum), (upper_count, upper_sum)] = self
                .fold_lessthan_indices_with_count(
                    [lower, upper],
                    [zero_range.clone(), one_range],
                    d,
                );
            let zero_sum = self.range_sum(level, zero_range.clone());
            return (
                zero_range.len() - lower_count + upper_count,
                M::operate(&M::rinv_operate(&zero_sum, &lower_sum), &upper_sum),
            );
        }
        (0, M::unit())
    }

    #[inline]
    fn range_sum(&self, level: usize, range: Range<usize>) -> M::T {
        let offset = self.offsets[level];
        M::rinv_operate(
            &self.prefix[offset + range.end],
            &self.prefix[offset + range.start],
        )
    }

    fn fold_lessthan_indices_with_count<const N: usize>(
        &self,
        indices: [usize; N],
        mut ranges: [Range<usize>; N],
        bits: usize,
    ) -> [(usize, M::T); N] {
        let mut results = std::array::from_fn(|_| (0, M::unit()));
        let last = indices
            .iter()
            .map(|index| index.trailing_zeros() as usize)
            .min()
            .unwrap_or(bits);
        for d in (last..bits).rev() {
            let level = self.wavelet_matrix.level(d);
            for ((&index, range), (count, sum)) in indices.iter().zip(&mut ranges).zip(&mut results)
            {
                let start1 = self.wavelet_matrix.bit_vectors[level].rank1(range.start);
                let end1 = self.wavelet_matrix.bit_vectors[level].rank1(range.end);
                let start0 = range.start - start1;
                let end0 = range.end - end1;
                if ((index >> d) & 1) != 0 {
                    *count += end0 - start0;
                    M::operate_assign(sum, &self.range_sum(level, start0..end0));
                    range.start = self.wavelet_matrix.zeros[level] + start1;
                    range.end = self.wavelet_matrix.zeros[level] + end1;
                } else {
                    range.start = start0;
                    range.end = end0;
                }
            }
        }
        results
    }

    /// Folds the weights below each query's threshold, traversing the queries together.
    pub fn fold_lessthan_batch(
        &self,
        queries: impl IntoIterator<Item = (T, Range<usize>)>,
    ) -> Vec<M::T> {
        let queries: Vec<_> = queries.into_iter().collect();
        let mut result = Vec::with_capacity(queries.len());
        for queries in queries.chunks(16) {
            let mut indices = [0; 16];
            let mut ranges = std::array::from_fn(|_| 0..0);
            for (i, (value, range)) in queries.iter().enumerate() {
                assert!(range.start <= range.end && range.end <= self.wavelet_matrix.len);
                indices[i] = self.wavelet_matrix.compress.index_lower_bound(value);
                ranges[i] = range.clone();
            }
            result.extend(
                self.fold_lessthan_indices_with_count(
                    indices,
                    ranges,
                    self.wavelet_matrix.bit_length,
                )
                .into_iter()
                .take(queries.len())
                .map(|(_, sum)| sum),
            );
        }
        result
    }

pub fn fold_lessthan_batch( &self, queries: impl IntoIterator<Item = (T, Range<usize>)>, ) -> Vec<M::T>

Folds the weights below each query’s threshold, traversing the queries together.

Examples found in repository

crates/library_checker/src/data_structure/rectangle_sum.rs (lines 22-27)

pub fn rectangle_sum(reader: impl Read, writer: impl Write) {
    prepare_io!(buffered; reader, writer);
    sc!(n, q, mut xyw: [(u32, u32, i64); n], queries: [(u32, u32, u32, u32); q]);
    xyw.radix_sort_by_key(|&(x, ..)| x);
    let xs: Vec<_> = xyw.iter().map(|&(x, ..)| x).collect();
    let search = StaticSearch::from_sorted(&xs);
    let endpoints: Vec<_> = queries.iter().flat_map(|&(l, _, r, _)| [l, r]).collect();
    let mut positions = vec![0; endpoints.len()];
    search.lower_bound_batch(&endpoints, &mut positions);
    let ys = xyw.iter().map(|&(_, y, _)| y).collect();
    let weights: Vec<_> = xyw.iter().map(|&(_, _, w)| w).collect();
    let wm = WaveletMatrix::new(ys);
    let fold = wm.build_fold::<AdditiveOperation<i64>>(&weights);
    let result = fold.fold_lessthan_batch(
        queries
            .into_iter()
            .zip(positions.as_chunks::<2>().0)
            .flat_map(|((_, d, _, u), &[l, r])| [(d, l..r), (u, l..r)]),
    );
    for &[lower, upper] in result.as_chunks::<2>().0 {
        pp!(upper - lower);
    }
}

Trait Implementations

impl<'a, T, M> Clone for WaveletMatrixFold<'a, T, M>

where T: Ord + Clone + Clone, M: AbelianGroup + Clone, M::T: Clone,

fn clone(&self) -> Self

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<'a, T, M> Debug for WaveletMatrixFold<'a, T, M>

where T: Ord + Clone + Debug, M: AbelianGroup + Debug, M::T: Debug,

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

Formats the value using the given formatter.