Struct CompressedSegmentTree 

pub struct CompressedSegmentTree<M, X, Inner>
where
    M: Monoid,
{
    compress: Vec<X>,
    segs: Vec<Inner>,
    _marker: PhantomData<fn() -> M>,
}

Fields

compress: Vec<X>

segs: Vec<Inner>

_marker: PhantomData<fn() -> M>

Implementations

impl<M, X> CompressedSegmentTree<M, X, Tag<M>>

where M: Monoid, X: Clone + Ord,

fn merge_1d_coordinates(left: &Self, right: &Self) -> Self

impl<M, T1> CompressedSegmentTree<M, T1, Tag<M>>

where M: Monoid, T1: Clone + Ord,

pub fn new(points: &[(T1,)]) -> Self

fn from_iter<'a, Iter>(points: Iter) -> Self

where T1: 'a, Iter: IntoIterator<Item = &'a (T1,)> + Clone,

pub fn fold<Q1>(&self, range: &(Q1,)) -> M::T

where Q1: RangeBounds<T1>,

pub fn update(&mut self, key: &(T1,), x: &M::T)

pub fn partition_point_acc<P>(&self, left: &T1, pred: P) -> (Option<&T1>, M::T)

where P: FnMut(&M::T) -> bool,

pub fn rpartition_point_acc<P>( &self, right: &T1, pred: P, ) -> (Option<&T1>, M::T)

where P: FnMut(&M::T) -> bool,

impl<M, T1, T2> CompressedSegmentTree<M, T1, CompressedSegmentTree<M, T2, Tag<M>>>

where M: Monoid, T1: Clone + Ord, T2: Clone + Ord,

pub fn new(points: &[(T1, (T2,))]) -> Self

Examples found in repository

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

pub fn point_add_rectangle_sum_compressed_segment_tree(reader: impl Read, writer: impl Write) {
    prepare_io!(reader, writer);
    sc!(n, q, xyw: [(u32, u32, u64); n], queries: [Query; q]);
    let points: Vec<_> = xyw
        .iter()
        .map(|&(x, y, _)| (x, (y,)))
        .chain(queries.iter().filter_map(|&query| {
            if let Query::Add { x, y, .. } = query {
                Some((x, (y,)))
            } else {
                None
            }
        }))
        .collect();

    let mut seg = CompressedSegmentTree2d::<AdditiveOperation<u64>, _, _>::new(&points);
    for &(x, y, w) in &xyw {
        seg.update(&(x, (y,)), &w);
    }

    for query in queries {
        match query {
            Query::Add { x, y, w } => {
                seg.update(&(x, (y,)), &w);
            }
            Query::Sum { l, d, r, u } => {
                let ans = seg.fold(&(l..r, (d..u,)));
                pp!(ans);
            }
        }
    }
}

fn from_iter<'a, Iter>(points: Iter) -> Self

where T1: 'a, T2: 'a, Iter: IntoIterator<Item = &'a (T1, (T2,))> + Clone,

pub fn fold<Q1, Q2>(&self, range: &(Q1, (Q2,))) -> M::T

where Q1: RangeBounds<T1>, Q2: RangeBounds<T2>,

Examples found in repository

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

pub fn point_add_rectangle_sum_compressed_segment_tree(reader: impl Read, writer: impl Write) {
    prepare_io!(reader, writer);
    sc!(n, q, xyw: [(u32, u32, u64); n], queries: [Query; q]);
    let points: Vec<_> = xyw
        .iter()
        .map(|&(x, y, _)| (x, (y,)))
        .chain(queries.iter().filter_map(|&query| {
            if let Query::Add { x, y, .. } = query {
                Some((x, (y,)))
            } else {
                None
            }
        }))
        .collect();

    let mut seg = CompressedSegmentTree2d::<AdditiveOperation<u64>, _, _>::new(&points);
    for &(x, y, w) in &xyw {
        seg.update(&(x, (y,)), &w);
    }

    for query in queries {
        match query {
            Query::Add { x, y, w } => {
                seg.update(&(x, (y,)), &w);
            }
            Query::Sum { l, d, r, u } => {
                let ans = seg.fold(&(l..r, (d..u,)));
                pp!(ans);
            }
        }
    }
}

pub fn update(&mut self, key: &(T1, (T2,)), x: &M::T)

Examples found in repository

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

pub fn point_add_rectangle_sum_compressed_segment_tree(reader: impl Read, writer: impl Write) {
    prepare_io!(reader, writer);
    sc!(n, q, xyw: [(u32, u32, u64); n], queries: [Query; q]);
    let points: Vec<_> = xyw
        .iter()
        .map(|&(x, y, _)| (x, (y,)))
        .chain(queries.iter().filter_map(|&query| {
            if let Query::Add { x, y, .. } = query {
                Some((x, (y,)))
            } else {
                None
            }
        }))
        .collect();

    let mut seg = CompressedSegmentTree2d::<AdditiveOperation<u64>, _, _>::new(&points);
    for &(x, y, w) in &xyw {
        seg.update(&(x, (y,)), &w);
    }

    for query in queries {
        match query {
            Query::Add { x, y, w } => {
                seg.update(&(x, (y,)), &w);
            }
            Query::Sum { l, d, r, u } => {
                let ans = seg.fold(&(l..r, (d..u,)));
                pp!(ans);
            }
        }
    }
}

pub fn partition_point_acc<P, Q2>( &self, left: &T1, inner_ranges: &(Q2,), pred: P, ) -> (Option<&T1>, M::T)

where P: FnMut(&M::T) -> bool, Q2: RangeBounds<T2>,

pub fn rpartition_point_acc<P, Q2>( &self, right: &T1, inner_ranges: &(Q2,), pred: P, ) -> (Option<&T1>, M::T)

where P: FnMut(&M::T) -> bool, Q2: RangeBounds<T2>,

impl<M, T1, T2, T3> CompressedSegmentTree<M, T1, CompressedSegmentTree<M, T2, CompressedSegmentTree<M, T3, Tag<M>>>>

where M: Monoid, T1: Clone + Ord, T2: Clone + Ord, T3: Clone + Ord,

pub fn new(points: &[(T1, (T2, (T3,)))]) -> Self

fn from_iter<'a, Iter>(points: Iter) -> Self

where T1: 'a, T2: 'a, T3: 'a, Iter: IntoIterator<Item = &'a (T1, (T2, (T3,)))> + Clone,

pub fn fold<Q1, Q2, Q3>(&self, range: &(Q1, (Q2, (Q3,)))) -> M::T

where Q1: RangeBounds<T1>, Q2: RangeBounds<T2>, Q3: RangeBounds<T3>,

pub fn update(&mut self, key: &(T1, (T2, (T3,))), x: &M::T)

pub fn partition_point_acc<P, Q2, Q3>( &self, left: &T1, inner_ranges: &(Q2, (Q3,)), pred: P, ) -> (Option<&T1>, M::T)

where P: FnMut(&M::T) -> bool, Q2: RangeBounds<T2>, Q3: RangeBounds<T3>,

pub fn rpartition_point_acc<P, Q2, Q3>( &self, right: &T1, inner_ranges: &(Q2, (Q3,)), pred: P, ) -> (Option<&T1>, M::T)

where P: FnMut(&M::T) -> bool, Q2: RangeBounds<T2>, Q3: RangeBounds<T3>,

impl<M, T1, T2, T3, T4> CompressedSegmentTree<M, T1, CompressedSegmentTree<M, T2, CompressedSegmentTree<M, T3, CompressedSegmentTree<M, T4, Tag<M>>>>>

where M: Monoid, T1: Clone + Ord, T2: Clone + Ord, T3: Clone + Ord, T4: Clone + Ord,

pub fn new(points: &[(T1, (T2, (T3, (T4,))))]) -> Self

fn from_iter<'a, Iter>(points: Iter) -> Self

where T1: 'a, T2: 'a, T3: 'a, T4: 'a, Iter: IntoIterator<Item = &'a (T1, (T2, (T3, (T4,))))> + Clone,

pub fn fold<Q1, Q2, Q3, Q4>(&self, range: &(Q1, (Q2, (Q3, (Q4,))))) -> M::T

where Q1: RangeBounds<T1>, Q2: RangeBounds<T2>, Q3: RangeBounds<T3>, Q4: RangeBounds<T4>,

pub fn update(&mut self, key: &(T1, (T2, (T3, (T4,)))), x: &M::T)

pub fn partition_point_acc<P, Q2, Q3, Q4>( &self, left: &T1, inner_ranges: &(Q2, (Q3, (Q4,))), pred: P, ) -> (Option<&T1>, M::T)

where P: FnMut(&M::T) -> bool, Q2: RangeBounds<T2>, Q3: RangeBounds<T3>, Q4: RangeBounds<T4>,

pub fn rpartition_point_acc<P, Q2, Q3, Q4>( &self, right: &T1, inner_ranges: &(Q2, (Q3, (Q4,))), pred: P, ) -> (Option<&T1>, M::T)

where P: FnMut(&M::T) -> bool, Q2: RangeBounds<T2>, Q3: RangeBounds<T3>, Q4: RangeBounds<T4>,

Trait Implementations

impl<M, X, Inner> Clone for CompressedSegmentTree<M, X, Inner>

where M: Monoid, X: Clone, Inner: Clone,

fn clone(&self) -> Self

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<M, X, Inner> Debug for CompressedSegmentTree<M, X, Inner>

where M: Monoid, X: Debug, Inner: Debug,

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

Formats the value using the given formatter.

impl<M, X, Inner> Default for CompressedSegmentTree<M, X, Inner>

where M: Monoid,

fn default() -> Self

Returns the “default value” for a type.

impl<M, X, Inner> MergeCoordinates<M> for CompressedSegmentTree<M, X, Inner>

where M: Monoid, X: Clone + Ord, Inner: MergeCoordinates<M>,

fn empty() -> Self

fn merge_coordinates(left: &Self, right: &Self) -> Self