Struct WaveletMatrixFold 

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

Fields

wavelet_matrix: &'a WaveletMatrix<T>

prefix: Vec<M::T>

Implementations

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

where T: Ord + Clone, M: AbelianGroup,

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

Examples found in repository

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

    pub fn fold_lessthan_with_count(&self, val: T, mut range: Range<usize>) -> (usize, M::T) {
        debug_assert!(range.end <= self.wavelet_matrix.len);
        let idx = self.wavelet_matrix.compress.index_lower_bound(&val);
        let mut count = 0;
        let mut sum = M::unit();
        for d in (0..self.wavelet_matrix.bit_length).rev() {
            let level = self.wavelet_matrix.level(d);
            let start0 = self.wavelet_matrix.rank0(level, range.start);
            let end0 = self.wavelet_matrix.rank0(level, range.end);
            if ((idx >> d) & 1) != 0 {
                count += end0 - start0;
                sum = M::operate(&sum, &self.range_sum(level + 1, start0..end0));
                range.start = self.wavelet_matrix.zeros[level] + (range.start - start0);
                range.end = self.wavelet_matrix.zeros[level] + (range.end - end0);
            } else {
                range.start = start0;
                range.end = end0;
            }
        }
        (count, sum)
    }

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

Examples found in repository

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

    pub fn fold_range(&self, valrange: Range<T>, range: Range<usize>) -> M::T {
        M::rinv_operate(
            &self.fold_lessthan(valrange.end, range.clone()),
            &self.fold_lessthan(valrange.start, range),
        )
    }

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 346)

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

    pub fn fold_lessthan_with_count(&self, val: T, mut range: Range<usize>) -> (usize, M::T) {
        debug_assert!(range.end <= self.wavelet_matrix.len);
        let idx = self.wavelet_matrix.compress.index_lower_bound(&val);
        let mut count = 0;
        let mut sum = M::unit();
        for d in (0..self.wavelet_matrix.bit_length).rev() {
            let level = self.wavelet_matrix.level(d);
            let start0 = self.wavelet_matrix.rank0(level, range.start);
            let end0 = self.wavelet_matrix.rank0(level, range.end);
            if ((idx >> d) & 1) != 0 {
                count += end0 - start0;
                sum = M::operate(&sum, &self.range_sum(level + 1, start0..end0));
                range.start = self.wavelet_matrix.zeros[level] + (range.start - start0);
                range.end = self.wavelet_matrix.zeros[level] + (range.end - end0);
            } else {
                range.start = start0;
                range.end = end0;
            }
        }
        (count, sum)
    }

    pub fn fold_range(&self, valrange: Range<T>, range: Range<usize>) -> M::T {
        M::rinv_operate(
            &self.fold_lessthan(valrange.end, range.clone()),
            &self.fold_lessthan(valrange.start, range),
        )
    }

    pub fn fold_range_with_count(&self, valrange: Range<T>, range: Range<usize>) -> (usize, M::T) {
        let (count_upper, sum_upper) = self.fold_lessthan_with_count(valrange.end, range.clone());
        let (count_lower, sum_lower) = self.fold_lessthan_with_count(valrange.start, range);
        (
            count_upper - count_lower,
            M::rinv_operate(&sum_upper, &sum_lower),
        )
    }

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

pub fn static_range_sum_with_upper_bound(reader: impl Read, mut writer: impl Write) {
    let s = read_all_unchecked(reader);
    let mut scanner = Scanner::new(&s);
    scan!(scanner, 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 {
        scan!(scanner, l, r, x: i64);
        let (count, sum) = fold.fold_lessthan_with_count(x + 1, l..r);
        writeln!(writer, "{} {}", count, sum).ok();
    }
}

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)

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) -> WaveletMatrixFold<'a, T, M>

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.