Struct LazySegTree

Source

pub struct LazySegTree<M: Monoid + Clone, A: Monoid + Act<M> + Clone>(/* private fields */);

Expand description

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§

Source §

impl<M: Monoid + Clone, A: Monoid + Act<M> + Clone> LazySegTree<M, A>

Source

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);

Source

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));

Source

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));

Source

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));

Source

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));