Struct libpuri::LazySegTree

pub struct LazySegTree<M: Monoid, A: LazyAct<M>>(_);

A segment tree that supports range query and range update.

A lazy segment requires a Monoid that represents a property of intervals and another monoid that represents a range operation. The latter should also conform to a LazyAct which defines how the range operation should be applied to a range. Check out the documentation of both traits for further details.

Examples

Following example supports two operations:

• Query minimum and maximum numbers within an interval.
• Add a number to each element within an interval.

use libpuri::{Monoid, LazyAct, LazySegTree};

#[derive(Clone, Debug, PartialEq, Eq)]
struct MinMax(i64, i64);
impl Monoid for MinMax {
    const ID: Self = MinMax(i64::MAX, i64::MIN);
    fn op(&self, rhs: &Self) -> Self {
        MinMax(self.0.min(rhs.0), self.1.max(rhs.1))
    }
}

#[derive(Clone, Debug, PartialEq, Eq)]
struct Add(i64);
impl Monoid for Add {
    const ID: Self = Add(0);
    fn op(&self, rhs: &Self) -> Self {
        Add(self.0.saturating_add(rhs.0))
    }
}

impl LazyAct<MinMax> for Add {
    fn act(&self, m: &MinMax) -> MinMax {
        if m == &MinMax::ID {
            MinMax::ID
        } else {
            MinMax(m.0 + self.0, m.1 + self.0)
        }
    }
}

// Initialize with [0, 0, 0, 0, 0, 0]
let mut lazy_tree: LazySegTree<MinMax, Add> = (0..6).map(|_| MinMax(0, 0)).collect();
assert_eq!(lazy_tree.get(..), MinMax(0, 0));

// Range update [5, 5, 5, 5, 0, 0]
lazy_tree.act(0..4, Add(5));

// Another range update [5, 5, 47, 47, 42, 42]
lazy_tree.act(2..6, Add(42));

assert_eq!(lazy_tree.get(1..3), MinMax(5,  47));
assert_eq!(lazy_tree.get(3..5), MinMax(42, 47));

// Set index 3 to 0 [5, 5, 47, 0, 42, 42]
lazy_tree.set(3, MinMax(0, 0));

assert_eq!(lazy_tree.get(..), MinMax(0,  47));
assert_eq!(lazy_tree.get(3..5), MinMax(0,  42));
assert_eq!(lazy_tree.get(0), MinMax(5, 5));

Implementations

impl<M: Monoid, A: LazyAct<M>> LazySegTree<M, A>

pub fn new(size: usize) -> Self

Constructs a new lazy segment tree with at least given number of intervals can be stored.

The segment tree will be initialized with the identity elements.

Complexity

O(n).

If you know the initial elements in advance, collect() should be preferred over new(). Initializing with the identity elements and updating n elements will tax you O(nlog(n)), whereas collect() implementation is O(n) by computing the interval properties only once.

Examples

let mut lazy_tree: LazySegTree<MinMax, Add> = LazySegTree::new(5);

// Initialized with [id, id, id, id, id]
assert_eq!(lazy_tree.get(..), MinMax::ID);

pub fn get<R>(&mut self, range: R) -> M where
    R: IntoIndex, 

Queries on the given interval.

Note that any RangeBounds can be used including .., a.., ..b, ..=c, d..e, or f..=g. You can just seg_tree.get(..) to get the interval property of the entire elements and lazy_tree.get(a) to get a specific element.

Examples

// [0, 42, 6, 7, 2]
let mut lazy_tree: LazySegTree<MinMax, Add> = [0, 42, 6, 7, 2].iter()
    .map(|&n| MinMax(n, n))
    .collect();

assert_eq!(lazy_tree.get(..), MinMax(0, 42));

// [5, 47, 11, 7, 2]
lazy_tree.act(0..3, Add(5));

// [5, 47, 4, 0, -5]
lazy_tree.act(2..5, Add(-7));

assert_eq!(lazy_tree.get(..), MinMax(-5, 47));
assert_eq!(lazy_tree.get(..4), MinMax(0, 47));
assert_eq!(lazy_tree.get(2), MinMax(4, 4));

pub fn set(&mut self, i: usize, m: M)

Sets an element with given index to the value. It propagates its update to its ancestors.

It takes O(log(n)) to propagate the update as the height of the tree is log(n).

Examples

// [0, 42, 6, 7, 2]
let mut lazy_tree: LazySegTree<MinMax, Add> = [0, 42, 6, 7, 2].iter()
    .map(|&n| MinMax(n, n))
    .collect();

assert_eq!(lazy_tree.get(..), MinMax(0, 42));

// [0, 1, 6, 7, 2]
lazy_tree.set(1, MinMax(1, 1));

assert_eq!(lazy_tree.get(1), MinMax(1, 1));
assert_eq!(lazy_tree.get(..), MinMax(0, 7));
assert_eq!(lazy_tree.get(2..), MinMax(2, 7));

pub fn act<R>(&mut self, range: R, a: A) where
    R: IntoIndex, 

Apply an action to elements within given range.

It takes O(log(n)).

Examples

// [0, 42, 6, 7, 2]
let mut lazy_tree: LazySegTree<MinMax, Add> = [0, 42, 6, 7, 2].iter()
    .map(|&n| MinMax(n, n))
    .collect();

assert_eq!(lazy_tree.get(..), MinMax(0, 42));

// [0, 30, -6, 7, 2]
lazy_tree.act(1..3, Add(-12));

assert_eq!(lazy_tree.get(1), MinMax(30, 30));
assert_eq!(lazy_tree.get(..), MinMax(-6, 30));
assert_eq!(lazy_tree.get(2..), MinMax(-6, 7));

Trait Implementations

impl<M, A> Debug for LazySegTree<M, A> where
    M: Debug + Monoid,
    A: Debug + LazyAct<M>, 

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

Formats the value using the given formatter.

impl<M, A> FromIterator<M> for LazySegTree<M, A> where
    M: Monoid,
    A: LazyAct<M>, 

You can collect into a lazy segment tree.

pub fn from_iter<I: IntoIterator<Item = M>>(iter: I) -> Self

Creates a value from an iterator.