Struct AssignSegmentTree 

pub struct AssignSegmentTree<Query>
where
    Query: Monoid<Set: Clone>,
{ /* private fields */ }

A data structure that supports range query range assign operations.

Example

use seg_lib::{AssignSegmentTree, ops::BitXor};

/// Demonstrates how to use an [`AssignSegmentTree`] for:
/// - range XOR queries
/// - range assign updates
fn main() {
    // Initialize a segment tree with values 0..100
    let mut seg = AssignSegmentTree::<BitXor<u32>>::from_iter(0..100);
    assert_eq!(seg.len(), 100);
    assert_eq!(Vec::from_iter(seg.iter().copied()), Vec::from_iter(0..100));

    // Assign values to a range
    seg.range_assign(..50, 100);
    assert!(seg.iter().take(50).all(|e| *e == 100));

    // Query XOR over ranges
    assert_eq!(seg.range_query(..50), 0); // 50 is even, so XOR cancels out
    assert_eq!(seg.range_query(50..), (50..100).fold(0, |res, e| res ^ e));

    // Assign and query a single element
    seg.point_assign(50, !0);
    assert_eq!(seg.point_query(50), &!0);
}

Implementations

impl<Query> AssignSegmentTree<Query>

where Query: Monoid<Set: Clone>,

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::{AssignSegmentTree, ops::LCM};

let ast = AssignSegmentTree::<LCM<i32>>::new(100);

pub fn len(&self) -> usize

Returns the number of elements.

Time complexity

O(1)

Example

use seg_lib::{AssignSegmentTree, ops::Max};

let ast = AssignSegmentTree::<Max<i32>>::new(100);
assert_eq!(ast.len(), 100);

Examples found in repository

examples/ex_assign.rs (line 9)

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

    // Assign values to a range
    seg.range_assign(..50, 100);
    assert!(seg.iter().take(50).all(|e| *e == 100));

    // Query XOR over ranges
    assert_eq!(seg.range_query(..50), 0); // 50 is even, so XOR cancels out
    assert_eq!(seg.range_query(50..), (50..100).fold(0, |res, e| res ^ e));

    // Assign and query a single element
    seg.point_assign(50, !0);
    assert_eq!(seg.point_query(50), &!0);
}

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

Returns an iterator over the elements

Time complexity

O(N)

Example

use seg_lib::{AssignSegmentTree, ops::Min};

let mut ast = AssignSegmentTree::<Min<i32>>::new(100);
assert!(ast.iter().all(|e| e.is_none()));

Examples found in repository

examples/ex_assign.rs (line 10)

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

    // Assign values to a range
    seg.range_assign(..50, 100);
    assert!(seg.iter().take(50).all(|e| *e == 100));

    // Query XOR over ranges
    assert_eq!(seg.range_query(..50), 0); // 50 is even, so XOR cancels out
    assert_eq!(seg.range_query(50..), (50..100).fold(0, |res, e| res ^ e));

    // Assign and query a single element
    seg.point_assign(50, !0);
    assert_eq!(seg.point_query(50), &!0);
}

pub fn range_assign<R>(&mut self, range: R, element: <Query as Monoid>::Set)

where R: RangeBounds<usize>,

Assigns the element over the range.

Time complexity

O(log N)

Example

use seg_lib::{AssignSegmentTree, ops::Add};

let mut ast = AssignSegmentTree::<Add<i32>>::from_iter(0..100);
assert_eq!(ast.range_query(..), 99 * 100 / 2);

ast.range_assign(.., 1);
assert!(ast.iter().all(|e| *e == 1))

Examples found in repository

examples/ex_assign.rs (line 13)

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

    // Assign values to a range
    seg.range_assign(..50, 100);
    assert!(seg.iter().take(50).all(|e| *e == 100));

    // Query XOR over ranges
    assert_eq!(seg.range_query(..50), 0); // 50 is even, so XOR cancels out
    assert_eq!(seg.range_query(50..), (50..100).fold(0, |res, e| res ^ e));

    // Assign and query a single element
    seg.point_assign(50, !0);
    assert_eq!(seg.point_query(50), &!0);
}

pub fn point_assign(&mut self, i: usize, element: <Query as Monoid>::Set)

Assign the element to the i-th node.

Does nothing if the range is empty.

Time complexity

O(log N)

Example

use seg_lib::{AssignSegmentTree, ops::BitOr};

let mut ast = AssignSegmentTree::<BitOr<u32>>::from(vec![0; 100]);
assert_eq!(ast.range_query(..), 0);

ast.point_assign(50, 999);
ast.point_assign(50, 99);
assert_eq!(ast.point_query(50), &99);

Examples found in repository

examples/ex_assign.rs (line 21)

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

    // Assign values to a range
    seg.range_assign(..50, 100);
    assert!(seg.iter().take(50).all(|e| *e == 100));

    // Query XOR over ranges
    assert_eq!(seg.range_query(..50), 0); // 50 is even, so XOR cancels out
    assert_eq!(seg.range_query(50..), (50..100).fold(0, |res, e| res ^ e));

    // Assign and query a single element
    seg.point_assign(50, !0);
    assert_eq!(seg.point_query(50), &!0);
}

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

where R: RangeBounds<usize>,

Answers a query over the given range.

Returns the identity element if the range is empty.

Unbounded bounds are clamped to the tree’s range.

Panics

Panics if the range is explicitly out of bounds.

Time complexity

O(log N)

Example

use seg_lib::{AssignSegmentTree, ops::Mul};

let mut ast = AssignSegmentTree::<Mul<i32>>::new(100);
assert_eq!(ast.range_query(..), 1);

ast.point_assign(20, 2);
ast.point_assign(30, 3);
assert_eq!(ast.range_query(..), 2 * 3);

ast.point_assign(30, 30);
assert_eq!(ast.range_query(20..=30), 2 * 30);

Examples found in repository

examples/ex_assign.rs (line 17)

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

    // Assign values to a range
    seg.range_assign(..50, 100);
    assert!(seg.iter().take(50).all(|e| *e == 100));

    // Query XOR over ranges
    assert_eq!(seg.range_query(..50), 0); // 50 is even, so XOR cancels out
    assert_eq!(seg.range_query(50..), (50..100).fold(0, |res, e| res ^ e));

    // Assign and query a single element
    seg.point_assign(50, !0);
    assert_eq!(seg.point_query(50), &!0);
}

pub fn point_query(&mut self, i: usize) -> &<Query 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::{AssignSegmentTree, ops::Add};

let mut ast = AssignSegmentTree::<Add<i32>>::from_iter(0..100);
assert_eq!(ast.point_query(50), &50);

ast.range_assign(.., 0);
assert_eq!(ast.point_query(50), &0);

Examples found in repository

examples/ex_assign.rs (line 22)

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

    // Assign values to a range
    seg.range_assign(..50, 100);
    assert!(seg.iter().take(50).all(|e| *e == 100));

    // Query XOR over ranges
    assert_eq!(seg.range_query(..50), 0); // 50 is even, so XOR cancels out
    assert_eq!(seg.range_query(50..), (50..100).fold(0, |res, e| res ^ e));

    // Assign and query a single element
    seg.point_assign(50, !0);
    assert_eq!(seg.point_query(50), &!0);
}

Trait Implementations

impl<Query> Clone for AssignSegmentTree<Query>

where Query: Monoid<Set: Clone>,

fn clone(&self) -> Self

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<Query> Debug for AssignSegmentTree<Query>

where Query: Monoid<Set: Clone + Debug>,

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

Formats the value using the given formatter.

impl<Query> From<Vec<<Query as Monoid>::Set>> for AssignSegmentTree<Query>

where Query: Monoid<Set: Clone>,

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

Converts to this type from the input type.

impl<Query> FromIterator<<Query as Monoid>::Set> for AssignSegmentTree<Query>

where Query: Monoid<Set: Clone>,

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

Creates a value from an iterator.