Struct SegmentTreeMap 

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

Fields

n: usize

seg: HashMap<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 66)

    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 bisect_perfect<F>(&self, mut pos: usize, mut acc: M::T, f: F) -> (usize, M::T)
    where
        F: Fn(&M::T) -> bool,
    {
        while pos < self.n {
            pos <<= 1;
            let nacc = M::operate(&acc, self.get_ref(pos));
            if !f(&nacc) {
                acc = nacc;
                pos += 1;
            }
        }
        (pos - self.n, acc)
    }
    fn rbisect_perfect<F>(&self, mut pos: usize, mut acc: M::T, f: F) -> (usize, M::T)
    where
        F: Fn(&M::T) -> bool,
    {
        while pos < self.n {
            pos = pos * 2 + 1;
            let nacc = M::operate(self.get_ref(pos), &acc);
            if !f(&nacc) {
                acc = nacc;
                pos -= 1;
            }
        }
        (pos - self.n, acc)
    }
    /// Returns the first index that satisfies a accumlative predicate.
    pub fn position_acc<R, F>(&self, range: R, f: F) -> Option<usize>
    where
        R: RangeBounds<usize>,
        F: Fn(&M::T) -> bool,
    {
        let range = range.to_range();
        debug_assert!(range.end <= self.n);
        let mut l = range.start + self.n;
        let r = range.end + 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 f(&nacc) {
                    return Some(self.bisect_perfect(l, acc, f).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 f(&nacc) {
                    return Some(self.bisect_perfect(r - 1, acc, f).0);
                }
                acc = nacc;
            }
        }
        None
    }
    /// Returns the last index that satisfies a accumlative predicate.
    pub fn rposition_acc<R, F>(&self, range: R, f: F) -> Option<usize>
    where
        R: RangeBounds<usize>,
        F: Fn(&M::T) -> bool,
    {
        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 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 f(&nacc) {
                    return Some(self.rbisect_perfect(r, acc, f).0);
                }
                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 f(&nacc) {
                    return Some(self.rbisect_perfect(l, acc, f).0);
                }
                acc = nacc;
            }
            c >>= 1;
        }
        None
    }

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 bisect_perfect<F>(&self, pos: usize, acc: M::T, f: F) -> (usize, M::T)

where F: Fn(&M::T) -> bool,

Examples found in repository

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

    pub fn position_acc<R, F>(&self, range: R, f: F) -> Option<usize>
    where
        R: RangeBounds<usize>,
        F: Fn(&M::T) -> bool,
    {
        let range = range.to_range();
        debug_assert!(range.end <= self.n);
        let mut l = range.start + self.n;
        let r = range.end + 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 f(&nacc) {
                    return Some(self.bisect_perfect(l, acc, f).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 f(&nacc) {
                    return Some(self.bisect_perfect(r - 1, acc, f).0);
                }
                acc = nacc;
            }
        }
        None
    }

fn rbisect_perfect<F>(&self, pos: usize, acc: M::T, f: F) -> (usize, M::T)

where F: Fn(&M::T) -> bool,

Examples found in repository

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

    pub fn rposition_acc<R, F>(&self, range: R, f: F) -> Option<usize>
    where
        R: RangeBounds<usize>,
        F: Fn(&M::T) -> bool,
    {
        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 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 f(&nacc) {
                    return Some(self.rbisect_perfect(r, acc, f).0);
                }
                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 f(&nacc) {
                    return Some(self.rbisect_perfect(l, acc, f).0);
                }
                acc = nacc;
            }
            c >>= 1;
        }
        None
    }

pub fn position_acc<R, F>(&self, range: R, f: F) -> Option<usize>

where R: RangeBounds<usize>, F: Fn(&M::T) -> bool,

Returns the first index that satisfies a accumlative predicate.

pub fn rposition_acc<R, F>(&self, range: R, f: F) -> Option<usize>

where R: RangeBounds<usize>, F: Fn(&M::T) -> bool,

Returns the last index that satisfies a accumlative predicate.

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.