Struct WaveletMatrixPointAdd 

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

Fields

wavelet_matrix: &'a WaveletMatrix<T>

bits: Vec<BinaryIndexedTree<M>>

Implementations

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

where T: Ord + Clone, M: AbelianGroup,

pub fn update(&mut self, index: usize, value: M::T)

Examples found in repository

crates/library_checker/src/data_structure/point_add_rectangle_sum.rs (line 46)

pub fn point_add_rectangle_sum(reader: impl Read, writer: impl Write) {
    prepare_io!(reader, writer);
    sc!(n, q, xyw: [(u32, u32, u64); iter n]);
    let mut points: Vec<_> = xyw.map(|(x, y, w)| (x, y, w as i64)).collect();
    sc!(queries: [Query; q]);
    points.extend(queries.iter().filter_map(|&query| match query {
        Query::Add { x, y, .. } => Some((x, y, 0)),
        Query::Sum { .. } => None,
    }));
    let mut order: Vec<_> = (0..points.len()).collect();
    order.radix_sort_by_key(|&i| points[i].0);
    let mut positions = vec![0; points.len()];
    let mut xs = Vec::with_capacity(points.len());
    let mut ys = Vec::with_capacity(points.len());
    let mut weights = Vec::with_capacity(points.len());
    for (i, &point) in order.iter().enumerate() {
        positions[point] = i;
        let (x, y, w) = points[point];
        xs.push(x);
        ys.push(y);
        weights.push(w);
    }
    let wm = WaveletMatrix::new(ys);
    let mut fold: WaveletMatrixPointAdd<_, AdditiveOperation<i64>> = wm.build_point_add(&weights);

    let mut point = n;
    for query in queries {
        match query {
            Query::Add { w, .. } => {
                fold.update(positions[point], w as i64);
                point += 1;
            }
            Query::Sum { l, d, r, u } => {
                let l = xs.partition_point(|&x| x < l);
                let r = xs.partition_point(|&x| x < r);
                pp!(fold.fold_range(d..u, l..r));
            }
        }
    }
}

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

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

Examples found in repository

crates/library_checker/src/data_structure/point_add_rectangle_sum.rs (line 52)

pub fn point_add_rectangle_sum(reader: impl Read, writer: impl Write) {
    prepare_io!(reader, writer);
    sc!(n, q, xyw: [(u32, u32, u64); iter n]);
    let mut points: Vec<_> = xyw.map(|(x, y, w)| (x, y, w as i64)).collect();
    sc!(queries: [Query; q]);
    points.extend(queries.iter().filter_map(|&query| match query {
        Query::Add { x, y, .. } => Some((x, y, 0)),
        Query::Sum { .. } => None,
    }));
    let mut order: Vec<_> = (0..points.len()).collect();
    order.radix_sort_by_key(|&i| points[i].0);
    let mut positions = vec![0; points.len()];
    let mut xs = Vec::with_capacity(points.len());
    let mut ys = Vec::with_capacity(points.len());
    let mut weights = Vec::with_capacity(points.len());
    for (i, &point) in order.iter().enumerate() {
        positions[point] = i;
        let (x, y, w) = points[point];
        xs.push(x);
        ys.push(y);
        weights.push(w);
    }
    let wm = WaveletMatrix::new(ys);
    let mut fold: WaveletMatrixPointAdd<_, AdditiveOperation<i64>> = wm.build_point_add(&weights);

    let mut point = n;
    for query in queries {
        match query {
            Query::Add { w, .. } => {
                fold.update(positions[point], w as i64);
                point += 1;
            }
            Query::Sum { l, d, r, u } => {
                let l = xs.partition_point(|&x| x < l);
                let r = xs.partition_point(|&x| x < r);
                pp!(fold.fold_range(d..u, l..r));
            }
        }
    }
}

fn fold_lessthan_index( &self, idx: usize, range: Range<usize>, bits: usize, ) -> M::T

Examples found in repository

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

    pub fn fold_range(&self, values: Range<T>, range: Range<usize>) -> M::T {
        let lower = self
            .wavelet_matrix
            .compress
            .index_lower_bound(&values.start);
        let upper = self.wavelet_matrix.compress.index_lower_bound(&values.end);
        if lower >= upper {
            return M::unit();
        }
        let mut range = range;
        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_sum = self.fold_lessthan_index(lower, zero_range.clone(), d);
            let upper_sum = self.fold_lessthan_index(upper, one_range, d);
            let zero_sum = self.bits[level].fold_abelian(zero_range.start, zero_range.end);
            let mut result = M::rinv_operate(&zero_sum, &lower_sum);
            M::operate_assign(&mut result, &upper_sum);
            return result;
        }
        M::unit()
    }