Struct DynamicSegmentTree

Source

pub struct DynamicSegmentTree<Query>where
    Query: Monoid,
{ /* private fields */ }

Expand description

A data structure that supports range query point update operations on large array.

§Example

use seg_lib::{DynamicSegmentTree, ops::LCM};

/// Demonstrates how to use a [`DynamicSegmentTree`] for:
/// - range LCM queries
/// - point updates (direct or functional)
fn main() {
    // Initialize a dynamic segment tree over -1000..5000
    let range = -1_000..5_000;
    let mut seg = DynamicSegmentTree::<LCM<i32>>::new(range.clone()).unwrap();
    assert_eq!(seg.len(), range.len());
    assert_eq!(seg.range_query(..), 1);

    // Update single elements
    seg.point_update(0, 2 * 3 * 7);
    seg.point_update(1_000, 3 * 7);
    seg.point_update(2_000, 2 * 5);

    // Query elements and ranges
    assert_eq!(seg.point_query(0), 2 * 3 * 7);
    assert_eq!(seg.range_query(..), 2 * 3 * 5 * 7);
    assert_eq!(seg.range_query(..1_000), 2 * 3 * 7);
}

Implementations§

Source §

impl<Query> DynamicSegmentTree<Query>
where Query: Monoid,

Source

pub fn new(range: Range<isize>) -> Option<Self>

Creates a new instance over the given range, initialized with identity elements.

Returns None if the range is empty.

If you know the total number of queries in advance, use with_capacity instead to avoid reallocations.

§Time complexity

O(1)

§Example

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

let mut dst = DynamicSegmentTree::<BitOr<u32>>::new(-100..100).unwrap();

Examples found in repository ?

examples/ex_dynamic.rs (line 9)

6fn main() {
7    // Initialize a dynamic segment tree over -1000..5000
8    let range = -1_000..5_000;
9    let mut seg = DynamicSegmentTree::<LCM<i32>>::new(range.clone()).unwrap();
10    assert_eq!(seg.len(), range.len());
11    assert_eq!(seg.range_query(..), 1);
12
13    // Update single elements
14    seg.point_update(0, 2 * 3 * 7);
15    seg.point_update(1_000, 3 * 7);
16    seg.point_update(2_000, 2 * 5);
17
18    // Query elements and ranges
19    assert_eq!(seg.point_query(0), 2 * 3 * 7);
20    assert_eq!(seg.range_query(..), 2 * 3 * 5 * 7);
21    assert_eq!(seg.range_query(..1_000), 2 * 3 * 7);
22}

Source

pub fn with_capacity(range: Range<isize>, q: usize) -> Option<Self>

Creates a new instance over the range with enough capacity to avoid reallocations for q queries., initialized with identity elements

Returns None if the given range is empty.

§Time complexity

O(1)

§Example

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

let num_query = 10_000;
// avoid reallocation
let mut dst = DynamicSegmentTree::<Add<i32>>::with_capacity(-100..100, num_query).unwrap();

Source

pub fn len(&self) -> usize

Returns the number of elements.

§Time complexity

O(1)

§Example

use seg_lib::{DynamicSegmentTree, ops::GCD};

let range = -100..100;
let mut dst = DynamicSegmentTree::<GCD<i32>>::new(range.clone()).unwrap();
assert_eq!(dst.len(), range.len());

// no effect
dst.point_update(0, 999);
assert_eq!(dst.len(), range.len());

Examples found in repository ?

examples/ex_dynamic.rs (line 10)

6fn main() {
7    // Initialize a dynamic segment tree over -1000..5000
8    let range = -1_000..5_000;
9    let mut seg = DynamicSegmentTree::<LCM<i32>>::new(range.clone()).unwrap();
10    assert_eq!(seg.len(), range.len());
11    assert_eq!(seg.range_query(..), 1);
12
13    // Update single elements
14    seg.point_update(0, 2 * 3 * 7);
15    seg.point_update(1_000, 3 * 7);
16    seg.point_update(2_000, 2 * 5);
17
18    // Query elements and ranges
19    assert_eq!(seg.point_query(0), 2 * 3 * 7);
20    assert_eq!(seg.range_query(..), 2 * 3 * 5 * 7);
21    assert_eq!(seg.range_query(..1_000), 2 * 3 * 7);
22}

Source

pub fn point_update(&mut self, i: isize, element: <Query 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::{DynamicSegmentTree, ops::Mul};

let mut dst = DynamicSegmentTree::<Mul<i32>>::new(-100..100).unwrap();
assert_eq!(dst.point_query(0), 1);

dst.point_update(0, 9);
assert_eq!(dst.point_query(0), 9);

Examples found in repository ?

examples/ex_dynamic.rs (line 14)

6fn main() {
7    // Initialize a dynamic segment tree over -1000..5000
8    let range = -1_000..5_000;
9    let mut seg = DynamicSegmentTree::<LCM<i32>>::new(range.clone()).unwrap();
10    assert_eq!(seg.len(), range.len());
11    assert_eq!(seg.range_query(..), 1);
12
13    // Update single elements
14    seg.point_update(0, 2 * 3 * 7);
15    seg.point_update(1_000, 3 * 7);
16    seg.point_update(2_000, 2 * 5);
17
18    // Query elements and ranges
19    assert_eq!(seg.point_query(0), 2 * 3 * 7);
20    assert_eq!(seg.range_query(..), 2 * 3 * 5 * 7);
21    assert_eq!(seg.range_query(..1_000), 2 * 3 * 7);
22}

Source

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

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

let mut dst = DynamicSegmentTree::<LCM<i32>>::new(-100..100).unwrap();

dst.point_update(-50, 9);
dst.point_update(-40, 3);
dst.point_update(-30, 7);

assert_eq!(dst.range_query(..), 9 * 7);
assert_eq!(dst.range_query(0..), 1);
assert_eq!(dst.range_query(..=-40), 9);

Examples found in repository ?

examples/ex_dynamic.rs (line 11)

6fn main() {
7    // Initialize a dynamic segment tree over -1000..5000
8    let range = -1_000..5_000;
9    let mut seg = DynamicSegmentTree::<LCM<i32>>::new(range.clone()).unwrap();
10    assert_eq!(seg.len(), range.len());
11    assert_eq!(seg.range_query(..), 1);
12
13    // Update single elements
14    seg.point_update(0, 2 * 3 * 7);
15    seg.point_update(1_000, 3 * 7);
16    seg.point_update(2_000, 2 * 5);
17
18    // Query elements and ranges
19    assert_eq!(seg.point_query(0), 2 * 3 * 7);
20    assert_eq!(seg.range_query(..), 2 * 3 * 5 * 7);
21    assert_eq!(seg.range_query(..1_000), 2 * 3 * 7);
22}

Source §

impl<Query> DynamicSegmentTree<Query>
where Query: Monoid<Set: Clone>,

Source

pub fn point_query(&self, i: isize) -> <Query as Monoid>::Set

Answers query for i-th element.

§Time complexity

O(log N)

§Example

use seg_lib::{DynamicSegmentTree, ops::BitAnd};

let mut dst = DynamicSegmentTree::<BitAnd<u32>>::new(-100..100).unwrap();

dst.point_update(-50, 9);
dst.point_update(-40, 3);
dst.point_update(-30, 7);

assert_eq!(dst.range_query(..), 9 & 3 & 7);
assert_eq!(dst.range_query(0..), !0);
assert_eq!(dst.range_query(..=-40), 9 & 3);

Examples found in repository ?

examples/ex_dynamic.rs (line 19)

6fn main() {
7    // Initialize a dynamic segment tree over -1000..5000
8    let range = -1_000..5_000;
9    let mut seg = DynamicSegmentTree::<LCM<i32>>::new(range.clone()).unwrap();
10    assert_eq!(seg.len(), range.len());
11    assert_eq!(seg.range_query(..), 1);
12
13    // Update single elements
14    seg.point_update(0, 2 * 3 * 7);
15    seg.point_update(1_000, 3 * 7);
16    seg.point_update(2_000, 2 * 5);
17
18    // Query elements and ranges
19    assert_eq!(seg.point_query(0), 2 * 3 * 7);
20    assert_eq!(seg.range_query(..), 2 * 3 * 5 * 7);
21    assert_eq!(seg.range_query(..1_000), 2 * 3 * 7);
22}