Struct libpuri::LazySegTree

pub struct LazySegTree<M: Monoid + Clone, A: Monoid + Act<M> + Clone>(_);

A segment tree that supports range query and range update.

Use a lazy segment tree when:

• You want to efficiently query on an interval property.
• You want to efficiently update properties in an interval.

Requirements

A lazy segment tree requires two monoids and an action of one on other like following:

• M: A monoid that represents the interval property.
• A: A monoid that reprenents the interval update.
• L: An action that represents the application of an update on a property.

For a lazy segment tree to work, the action should also satisfy the following property.

// An element `f` of `A` should be a homomorphism from `M` to `M`.
f(m * n) == f(m) * f(n)

This property cannot be checked by the compiler so the implementer should verify it by themself.

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, Act, LazySegTree};

#[derive(Clone, Debug, PartialEq, Eq)]
struct MinMax(i64, i64);

#[derive(Clone, Debug, PartialEq, Eq)]
struct Add(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))
    }
}

impl Monoid for Add {
    const ID: Self = Add(0);
    fn op(&self, rhs: &Self) -> Self {
        Add(self.0 + rhs.0)
    }
}

impl Act<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 + Clone, A: Monoid + Act<M> + Clone> 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, from_iter_sized() should be preferred over new().

Initializing with the identity elements and updating n elements will tax you O(nlog(n)), whereas from_iter_sized() 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 from_iter_sized<I: IntoIterator<Item = M>>(iter: I, size: usize) -> Self

Constructs a new lazy segment tree with given intervals properties.

Complexity

O(n).

Examples

let v = [0, 42, 17, 6, -11].iter().map(|&i| MinMax(i, i));
let mut lazy_tree: LazySegTree<MinMax, Add> = LazySegTree::from_iter_sized(v, 5);

// Initialized with [0, 42, 17, 6, -11]
assert_eq!(lazy_tree.get(..), MinMax(-11, 42));

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> FromIterator<M> for LazySegTree<M, A> where
    M: Monoid + Clone,
    A: Monoid + Act<M> + Clone, 

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.