Struct SegmentTreeMap 

pub struct SegmentTreeMap<M>
where
    M: Monoid,
{
    n: usize,
    seg: FibHashMap<usize, M::T>,
    u: M::T,
}

Fields

n: usize

seg: FibHashMap<usize, M::T>

u: M::T

Implementations

impl<M> SegmentTreeMap<M>

where M: Monoid,

pub fn new(n: usize) -> Self

fn get_ref(&self, k: usize) -> &M::T

Examples found in repository

crates/competitive/src/data_structure/segment_tree_map.rs (line 65)

    pub fn set(&mut self, k: usize, x: M::T) {
        debug_assert!(k < self.n);
        let mut k = k + self.n;
        *self.seg.entry(k).or_insert(M::unit()) = x;
        k /= 2;
        while k > 0 {
            *self.seg.entry(k).or_insert(M::unit()) =
                M::operate(self.get_ref(2 * k), self.get_ref(2 * k + 1));
            k /= 2;
        }
    }
    pub fn update(&mut self, k: usize, x: M::T) {
        debug_assert!(k < self.n);
        let mut k = k + self.n;
        let t = self.seg.entry(k).or_insert(M::unit());
        *t = M::operate(t, &x);
        k /= 2;
        while k > 0 {
            *self.seg.entry(k).or_insert(M::unit()) =
                M::operate(self.get_ref(2 * k), self.get_ref(2 * k + 1));
            k /= 2;
        }
    }
    pub fn get(&self, k: usize) -> M::T {
        debug_assert!(k < self.n);
        self.seg.get(&(k + self.n)).cloned().unwrap_or_else(M::unit)
    }
    pub fn fold<R>(&self, range: R) -> M::T
    where
        R: RangeBounds<usize>,
    {
        let range = range.to_range();
        debug_assert!(range.end <= self.n);
        let mut l = range.start + self.n;
        let mut r = range.end + self.n;
        let mut vl = M::unit();
        let mut vr = M::unit();
        while l < r {
            if l & 1 != 0 {
                vl = M::operate(&vl, self.get_ref(l));
                l += 1;
            }
            if r & 1 != 0 {
                r -= 1;
                vr = M::operate(self.get_ref(r), &vr);
            }
            l /= 2;
            r /= 2;
        }
        M::operate(&vl, &vr)
    }
    fn partition_point_perfect<P>(
        &self,
        mut pos: usize,
        mut acc: M::T,
        mut pred: P,
    ) -> (usize, M::T)
    where
        P: FnMut(&M::T) -> bool,
    {
        while pos < self.n {
            pos <<= 1;
            let nacc = M::operate(&acc, self.get_ref(pos));
            if pred(&nacc) {
                acc = nacc;
                pos += 1;
            }
        }
        (pos - self.n, acc)
    }
    fn rpartition_point_perfect<P>(
        &self,
        mut pos: usize,
        mut acc: M::T,
        mut pred: P,
    ) -> (usize, M::T)
    where
        P: FnMut(&M::T) -> bool,
    {
        while pos < self.n {
            pos = pos * 2 + 1;
            let nacc = M::operate(self.get_ref(pos), &acc);
            if pred(&nacc) {
                acc = nacc;
                pos -= 1;
            }
        }
        (pos - self.n, acc)
    }
    pub fn partition_point_acc<P>(&self, left: usize, mut pred: P) -> usize
    where
        P: FnMut(&M::T) -> bool,
    {
        let mut l = left + self.n;
        let r = 2 * self.n;
        let mut k = 0usize;
        let mut acc = M::unit();
        while l < r >> k {
            if l & 1 != 0 {
                let nacc = M::operate(&acc, self.get_ref(l));
                if !pred(&nacc) {
                    return self.partition_point_perfect(l, acc, pred).0;
                }
                acc = nacc;
                l += 1;
            }
            l >>= 1;
            k += 1;
        }
        for k in (0..k).rev() {
            let r = r >> k;
            if r & 1 != 0 {
                let nacc = M::operate(&acc, self.get_ref(r - 1));
                if !pred(&nacc) {
                    return self.partition_point_perfect(r - 1, acc, pred).0;
                }
                acc = nacc;
            }
        }
        self.n
    }
    pub fn rpartition_point_acc<P>(&self, right: usize, mut pred: P) -> usize
    where
        P: FnMut(&M::T) -> bool,
    {
        let mut l = self.n;
        let mut r = right + self.n;
        let mut c = 0usize;
        let mut k = 0usize;
        let mut acc = M::unit();
        while l >> k < r {
            c <<= 1;
            if l & (1 << k) != 0 {
                l += 1 << k;
                c += 1;
            }
            if r & 1 != 0 {
                r -= 1;
                let nacc = M::operate(self.get_ref(r), &acc);
                if !pred(&nacc) {
                    return self.rpartition_point_perfect(r, acc, pred).0 + 1;
                }
                acc = nacc;
            }
            r >>= 1;
            k += 1;
        }
        for k in (0..k).rev() {
            if c & 1 != 0 {
                l -= 1 << k;
                let l = l >> k;
                let nacc = M::operate(self.get_ref(l), &acc);
                if !pred(&nacc) {
                    return self.rpartition_point_perfect(l, acc, pred).0 + 1;
                }
                acc = nacc;
            }
            c >>= 1;
        }
        0
    }

pub fn set(&mut self, k: usize, x: M::T)

pub fn update(&mut self, k: usize, x: M::T)

pub fn get(&self, k: usize) -> M::T

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

where R: RangeBounds<usize>,

fn partition_point_perfect<P>( &self, pos: usize, acc: M::T, pred: P, ) -> (usize, M::T)

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

Examples found in repository

crates/competitive/src/data_structure/segment_tree_map.rs (line 159)

    pub fn partition_point_acc<P>(&self, left: usize, mut pred: P) -> usize
    where
        P: FnMut(&M::T) -> bool,
    {
        let mut l = left + self.n;
        let r = 2 * self.n;
        let mut k = 0usize;
        let mut acc = M::unit();
        while l < r >> k {
            if l & 1 != 0 {
                let nacc = M::operate(&acc, self.get_ref(l));
                if !pred(&nacc) {
                    return self.partition_point_perfect(l, acc, pred).0;
                }
                acc = nacc;
                l += 1;
            }
            l >>= 1;
            k += 1;
        }
        for k in (0..k).rev() {
            let r = r >> k;
            if r & 1 != 0 {
                let nacc = M::operate(&acc, self.get_ref(r - 1));
                if !pred(&nacc) {
                    return self.partition_point_perfect(r - 1, acc, pred).0;
                }
                acc = nacc;
            }
        }
        self.n
    }

fn rpartition_point_perfect<P>( &self, pos: usize, acc: M::T, pred: P, ) -> (usize, M::T)

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

Examples found in repository

crates/competitive/src/data_structure/segment_tree_map.rs (line 198)

    pub fn rpartition_point_acc<P>(&self, right: usize, mut pred: P) -> usize
    where
        P: FnMut(&M::T) -> bool,
    {
        let mut l = self.n;
        let mut r = right + self.n;
        let mut c = 0usize;
        let mut k = 0usize;
        let mut acc = M::unit();
        while l >> k < r {
            c <<= 1;
            if l & (1 << k) != 0 {
                l += 1 << k;
                c += 1;
            }
            if r & 1 != 0 {
                r -= 1;
                let nacc = M::operate(self.get_ref(r), &acc);
                if !pred(&nacc) {
                    return self.rpartition_point_perfect(r, acc, pred).0 + 1;
                }
                acc = nacc;
            }
            r >>= 1;
            k += 1;
        }
        for k in (0..k).rev() {
            if c & 1 != 0 {
                l -= 1 << k;
                let l = l >> k;
                let nacc = M::operate(self.get_ref(l), &acc);
                if !pred(&nacc) {
                    return self.rpartition_point_perfect(l, acc, pred).0 + 1;
                }
                acc = nacc;
            }
            c >>= 1;
        }
        0
    }

pub fn partition_point_acc<P>(&self, left: usize, pred: P) -> usize

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

pub fn rpartition_point_acc<P>(&self, right: usize, pred: P) -> usize

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

impl<M> SegmentTreeMap<M>

where M: AbelianMonoid,

pub fn fold_all(&self) -> M::T

Trait Implementations

impl<M> Clone for SegmentTreeMap<M>

where M: Monoid,

fn clone(&self) -> Self

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<M> Debug for SegmentTreeMap<M>

where M: Monoid<T: Debug>,

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

Formats the value using the given formatter.