Struct LazySegmentTree 

pub struct LazySegmentTree<Action>
where
    Action: MonoidAction,
{ /* private fields */ }

A data structure that supports range query range update operations.

Example

use seg_lib::{LazySegmentTree, acts::AddQueryMulUpdate};

/// Demonstrates how to use a [`LazySegmentTree`] for:
/// - range sum queries
/// - range multiplication updates
fn main() {
    // Initialize a lazy segment tree with values 0..100
    let mut seg = LazySegmentTree::<AddQueryMulUpdate<i32>>::from_iter(0..100);
    assert_eq!(seg.len(), 100);
    assert_eq!(Vec::from_iter(seg.iter().copied()), Vec::from_iter(0..100));

    // Apply a range update: x -> 2x
    seg.range_update(.., &2);
    assert_eq!(
        Vec::from_iter(seg.iter().copied()),
        (0..100).map(|i| i * 2).collect::<Vec<_>>()
    );

    // Query the sum over the first 50 elements
    assert_eq!(seg.range_query(..50), (0..50).map(|i| 2 * i).sum());

    // Update and query a single element
    seg.point_update(50, &100);
    assert_eq!(seg.point_query(50), &10_000);
}

Implementations

impl<Action> LazySegmentTree<Action>

where Action: MonoidAction,

pub fn new(n: usize) -> Self

Creates a new instance initialized with n identity elements.

If you want to initialize with specific values, use from or from_iter instead.

Time complexity

O(N)

Example

use seg_lib::{LazySegmentTree, acts::MaxQueryAddUpdate};

let lst = LazySegmentTree::<MaxQueryAddUpdate<i32>>::new(100);

pub fn len(&self) -> usize

Returns the number of elements.

Time complexity

O(1)

Example

use seg_lib::{LazySegmentTree, acts::MaxQueryAddUpdate};

let lst = LazySegmentTree::<MaxQueryAddUpdate<i32>>::new(100);
assert_eq!(lst.len(), 100);

Examples found in repository

examples/ex_lazy.rs (line 9)

fn main() {
    // Initialize a lazy segment tree with values 0..100
    let mut seg = LazySegmentTree::<AddQueryMulUpdate<i32>>::from_iter(0..100);
    assert_eq!(seg.len(), 100);
    assert_eq!(Vec::from_iter(seg.iter().copied()), Vec::from_iter(0..100));

    // Apply a range update: x -> 2x
    seg.range_update(.., &2);
    assert_eq!(
        Vec::from_iter(seg.iter().copied()),
        (0..100).map(|i| i * 2).collect::<Vec<_>>()
    );

    // Query the sum over the first 50 elements
    assert_eq!(seg.range_query(..50), (0..50).map(|i| 2 * i).sum());

    // Update and query a single element
    seg.point_update(50, &100);
    assert_eq!(seg.point_query(50), &10_000);
}

pub fn iter( &mut self, ) -> Iter<'_, <<Action as MonoidAction>::Set as Monoid>::Set>

Returns an iterator over the elements

Time complexity

O(N)

Example

use seg_lib::{LazySegmentTree, acts::MaxQueryAddUpdate};

let mut lst = LazySegmentTree::<MaxQueryAddUpdate<i32>>::new(100);
assert!(lst.iter().all(|v| v.is_none()));

Examples found in repository

examples/ex_lazy.rs (line 10)

fn main() {
    // Initialize a lazy segment tree with values 0..100
    let mut seg = LazySegmentTree::<AddQueryMulUpdate<i32>>::from_iter(0..100);
    assert_eq!(seg.len(), 100);
    assert_eq!(Vec::from_iter(seg.iter().copied()), Vec::from_iter(0..100));

    // Apply a range update: x -> 2x
    seg.range_update(.., &2);
    assert_eq!(
        Vec::from_iter(seg.iter().copied()),
        (0..100).map(|i| i * 2).collect::<Vec<_>>()
    );

    // Query the sum over the first 50 elements
    assert_eq!(seg.range_query(..50), (0..50).map(|i| 2 * i).sum());

    // Update and query a single element
    seg.point_update(50, &100);
    assert_eq!(seg.point_query(50), &10_000);
}

pub fn range_update<R>( &mut self, range: R, update: &<<Action as MonoidAction>::Map as Monoid>::Set, )

where R: RangeBounds<usize>,

Updates elements over the range using the specified binary operation.

Does nothing if the range is empty.

Time complexity

O(log N)

Example

use seg_lib::{LazySegmentTree, acts::MaxQueryAddUpdate};

let mut lst = LazySegmentTree::<MaxQueryAddUpdate<i32>>::from_iter(
    std::iter::repeat_n(Some(0), 100)
);
assert_eq!(lst.range_query(..), Some(0));

lst.range_update(..75, &100);
lst.range_update(25.., &110);
assert_eq!(lst.range_query(..25), Some(100));
assert_eq!(lst.range_query(..), Some(210));
assert_eq!(lst.range_query(75..), Some(110));

Examples found in repository

examples/ex_lazy.rs (line 13)

fn main() {
    // Initialize a lazy segment tree with values 0..100
    let mut seg = LazySegmentTree::<AddQueryMulUpdate<i32>>::from_iter(0..100);
    assert_eq!(seg.len(), 100);
    assert_eq!(Vec::from_iter(seg.iter().copied()), Vec::from_iter(0..100));

    // Apply a range update: x -> 2x
    seg.range_update(.., &2);
    assert_eq!(
        Vec::from_iter(seg.iter().copied()),
        (0..100).map(|i| i * 2).collect::<Vec<_>>()
    );

    // Query the sum over the first 50 elements
    assert_eq!(seg.range_query(..50), (0..50).map(|i| 2 * i).sum());

    // Update and query a single element
    seg.point_update(50, &100);
    assert_eq!(seg.point_query(50), &10_000);
}

pub fn point_update( &mut self, i: usize, update: &<<Action as MonoidAction>::Map as Monoid>::Set, )

Updates the i-th element using the specified binary operation.

Panics

Panics if i is out of bounds.

Time complexity

O(log N)

Example

use seg_lib::{LazySegmentTree, acts::MaxQueryAddUpdate};

let mut lst = LazySegmentTree::<MaxQueryAddUpdate<i32>>::from_iter(
    std::iter::repeat_n(Some(0), 100)
);
assert_eq!(lst.range_query(..), Some(0));

lst.point_update(25, &10);
lst.point_update(75, &20);
assert_eq!(lst.range_query(..), Some(20));
assert_eq!(lst.range_query(..50), Some(10))

Examples found in repository

examples/ex_lazy.rs (line 23)

fn main() {
    // Initialize a lazy segment tree with values 0..100
    let mut seg = LazySegmentTree::<AddQueryMulUpdate<i32>>::from_iter(0..100);
    assert_eq!(seg.len(), 100);
    assert_eq!(Vec::from_iter(seg.iter().copied()), Vec::from_iter(0..100));

    // Apply a range update: x -> 2x
    seg.range_update(.., &2);
    assert_eq!(
        Vec::from_iter(seg.iter().copied()),
        (0..100).map(|i| i * 2).collect::<Vec<_>>()
    );

    // Query the sum over the first 50 elements
    assert_eq!(seg.range_query(..50), (0..50).map(|i| 2 * i).sum());

    // Update and query a single element
    seg.point_update(50, &100);
    assert_eq!(seg.point_query(50), &10_000);
}

pub fn range_query<R>( &mut self, range: R, ) -> <<Action as MonoidAction>::Set as Monoid>::Set

where R: RangeBounds<usize>,

Answers a query over the range.

Returns the identity element if the range is empty.

Time complexity

O(log N)

Example

use seg_lib::{LazySegmentTree, acts::MaxQueryAddUpdate};

let mut lst = LazySegmentTree::<MaxQueryAddUpdate<i32>>::from_iter(
    (0..100).map(|v| Some(v))
);
assert_eq!(lst.range_query(..), Some(99));
assert_eq!(lst.range_query(..50), Some(49));
assert_eq!(lst.range_query(..=50), Some(50));
assert_eq!(lst.range_query(50..), Some(99));

Examples found in repository

examples/ex_lazy.rs (line 20)

fn main() {
    // Initialize a lazy segment tree with values 0..100
    let mut seg = LazySegmentTree::<AddQueryMulUpdate<i32>>::from_iter(0..100);
    assert_eq!(seg.len(), 100);
    assert_eq!(Vec::from_iter(seg.iter().copied()), Vec::from_iter(0..100));

    // Apply a range update: x -> 2x
    seg.range_update(.., &2);
    assert_eq!(
        Vec::from_iter(seg.iter().copied()),
        (0..100).map(|i| i * 2).collect::<Vec<_>>()
    );

    // Query the sum over the first 50 elements
    assert_eq!(seg.range_query(..50), (0..50).map(|i| 2 * i).sum());

    // Update and query a single element
    seg.point_update(50, &100);
    assert_eq!(seg.point_query(50), &10_000);
}

pub fn point_query( &mut self, i: usize, ) -> &<<Action as MonoidAction>::Set as Monoid>::Set

Returns the result of a query for the i-th element.

Panics

Panics if i is out of bounds.

Time complexity

O(log N)

Example

use seg_lib::{LazySegmentTree, acts::MaxQueryAddUpdate};

let mut lst = LazySegmentTree::<MaxQueryAddUpdate<i32>>::from_iter(
    (0..100).map(|v| Some(v))
);

for i in 0..100 {
    assert_eq!(lst.point_query(i), &Some(i as i32))
}

Examples found in repository

examples/ex_lazy.rs (line 24)

fn main() {
    // Initialize a lazy segment tree with values 0..100
    let mut seg = LazySegmentTree::<AddQueryMulUpdate<i32>>::from_iter(0..100);
    assert_eq!(seg.len(), 100);
    assert_eq!(Vec::from_iter(seg.iter().copied()), Vec::from_iter(0..100));

    // Apply a range update: x -> 2x
    seg.range_update(.., &2);
    assert_eq!(
        Vec::from_iter(seg.iter().copied()),
        (0..100).map(|i| i * 2).collect::<Vec<_>>()
    );

    // Query the sum over the first 50 elements
    assert_eq!(seg.range_query(..50), (0..50).map(|i| 2 * i).sum());

    // Update and query a single element
    seg.point_update(50, &100);
    assert_eq!(seg.point_query(50), &10_000);
}

Trait Implementations

impl<Action> Clone for LazySegmentTree<Action>

where <<Action as MonoidAction>::Set as Monoid>::Set: Clone, <<Action as MonoidAction>::Map as Monoid>::Set: Clone, Action: MonoidAction,

fn clone(&self) -> Self

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<Action> Debug for LazySegmentTree<Action>

where <<Action as MonoidAction>::Set as Monoid>::Set: Debug, <<Action as MonoidAction>::Map as Monoid>::Set: Debug, Action: MonoidAction,

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

Formats the value using the given formatter.

impl<Action> From<Vec<<<Action as MonoidAction>::Set as Monoid>::Set>> for LazySegmentTree<Action>

where Action: MonoidAction,

fn from(values: Vec<<<Action as MonoidAction>::Set as Monoid>::Set>) -> Self

Converts to this type from the input type.

impl<Action> FromIterator<<<Action as MonoidAction>::Set as Monoid>::Set> for LazySegmentTree<Action>

where Action: MonoidAction,

fn from_iter<T: IntoIterator<Item = <<Action as MonoidAction>::Set as Monoid>::Set>>( iter: T, ) -> Self

Creates a value from an iterator.