Struct LazySegTree 

pub struct LazySegTree<Spec: LazySegTreeSpec> { /* private fields */ }

Generic lazy segment tree.

The tree stores aggregates of type Spec::T and lazy tags of Spec::U. Supports efficient range queries and range updates in O(log n) time.

Type Parameters

• Spec - A type implementing LazySegTreeSpec that defines the operations

Implementations

impl<Spec: LazySegTreeSpec> LazySegTree<Spec>

pub fn new(size: usize) -> Self

Create a new tree of size elements, all initialized to Spec::ID.

The internal tree size (max_size) will be the next power of two greater than or equal to size for efficient tree operations.

Time Complexity

O(n) where n is the next power of two >= size.

Examples

use array_range_query::{LazySegTree, LazySegTreeSpec};
let tree = LazySegTree::<RangeAddSum>::new(100);
assert_eq!(tree.query(..), 0); // All elements start as identity (0)

pub fn from_vec(values: &[Spec::T]) -> Self

Build a tree from a slice of initial values.

The tree is constructed bottom-up in O(n) time, which is more efficient than creating an empty tree and updating each element individually.

Time Complexity

O(n) where n is the length of values.

Examples

use array_range_query::{LazySegTree, LazySegTreeSpec};
let values = vec![1, 2, 3, 4, 5];
let tree = LazySegTree::<RangeAddSum>::from_vec(&values);
assert_eq!(tree.query(..), 15); // Sum of all elements

Examples found in repository

examples/basic_usage.rs (line 158)

fn custom_lazy_example() {
    println!("4. Custom LazySegTree for Range Add + Range Sum");
    println!("----------------------------------------------");

    // Define a spec for range add operations with sum queries
    struct RangeAddSum;

    impl LazySegTreeSpec for RangeAddSum {
        type T = i64; // Data type (stores sums)
        type U = i64; // Update type (add values)
        const ID: Self::T = 0;

        // Combine two sum values
        fn op_on_data(d1: &mut Self::T, d2: &Self::T) {
            *d1 += *d2;
        }

        // Compose two add operations
        fn op_on_update(u1: &mut Self::U, u2: &Self::U) {
            *u1 += *u2;
        }

        // Apply add operation to sum (multiply by range size)
        fn op_update_on_data(u: &Self::U, d: &mut Self::T, size: usize) {
            *d += u * (size as i64);
        }
    }

    let values = vec![1i64, 2, 3, 4, 5];
    let mut lazy_tree = LazySegTree::<RangeAddSum>::from_vec(&values);

    println!("Initial values: {:?}", values);
    println!("Initial sum [1, 4): {}", lazy_tree.query(1..4)); // 2 + 3 + 4 = 9
    println!("Initial sum [0, 5): {}", lazy_tree.query(..)); // 15

    // Add 10 to all elements in range [1, 4)
    lazy_tree.update(1..4, 10);
    println!("\nAfter adding 10 to range [1, 4):");
    println!("Sum [1, 4): {}", lazy_tree.query(1..4)); // (2+10) + (3+10) + (4+10) = 39
    println!("Sum [0, 5): {}", lazy_tree.query(..)); // 1 + 12 + 13 + 14 + 5 = 45

    // Add 5 to range [0, 2)
    lazy_tree.update(..2, 5);
    println!("\nAfter adding 5 to range [0, 2):");
    println!("Sum [0, 2): {}", lazy_tree.query(..2)); // (1+5) + (12+5) = 23
    println!("Sum [0, 5): {}", lazy_tree.query(..)); // 6 + 17 + 13 + 14 + 5 = 55
    println!();
}

/// Example 5: Using LazySegTree helper types
fn lazy_helper_example() {
    println!("5. LazySegTree Helper Types");
    println!("--------------------------");

    // Range add + range sum
    let values = vec![2i32, 4, 6, 8, 10];
    let mut sum_tree = LazySegTreeAddSum::<i32>::from_vec(&values);

    println!("Initial values: {:?}", values);
    println!("Sum [0, 5): {}", sum_tree.query(..)); // 30
    println!("Sum [1, 4): {}", sum_tree.query(1..4)); // 4 + 6 + 8 = 18

    // Add 3 to range [1, 4)
    sum_tree.update(1..4, 3);
    println!("\nAfter adding 3 to range [1, 4):");
    println!("Sum [0, 5): {}", sum_tree.query(..)); // 2 + 7 + 9 + 11 + 10 = 39
    println!("Sum [1, 4): {}", sum_tree.query(1..4)); // 7 + 9 + 11 = 27

    // Add -2 to range [0, 3)
    sum_tree.update(..3, -2);
    println!("\nAfter subtracting 2 from range [0, 3):");
    println!("Sum [0, 5): {}", sum_tree.query(..)); // 0 + 5 + 7 + 11 + 10 = 33
    println!("Sum [0, 3): {}", sum_tree.query(..3)); // 0 + 5 + 7 = 12

    // Range add + range min
    let min_values = vec![5, 2, 8, 1, 9, 3];
    let mut min_tree = LazySegTreeAddMin::<i32>::from_vec(&min_values);
    println!("\nInitial min values: {:?}", min_values);
    println!("Min [0, 6): {}", min_tree.query(..)); // 1
    min_tree.update(1..4, 2);
    println!(
        "After adding 2 to [1, 4): Min [0, 6): {}",
        min_tree.query(..)
    ); // min(5, 4, 10, 3, 9, 3) = 3

    // Range assignment (replace) + range sum
    let rep_values = vec![1, 2, 3, 4, 5];
    let mut rep_tree = LazySegTreeReplaceSum::<i32>::from_vec(&rep_values);
    println!("\nInitial replace values: {:?}", rep_values);
    println!("Sum [0, 5): {}", rep_tree.query(..)); // 15
    rep_tree.update(1..4, 10); // Replace [1, 4) with 10
    println!(
        "After replacing [1, 4) with 10: Sum [0, 5): {}",
        rep_tree.query(..)
    ); // 1 + 10 + 10 + 10 + 5 = 36
    println!();
}

/// Example 6: Advanced lazy operations with overlapping updates
fn advanced_lazy_example() {
    println!("6. Advanced Lazy Operations");
    println!("--------------------------");

    let values = vec![1i32, 1, 1, 1, 1, 1, 1, 1]; // 8 ones
    let mut tree = LazySegTreeAddSum::<i32>::from_vec(&values);

    println!("Initial: 8 ones, sum = {}", tree.query(..));

    // Perform overlapping updates
    tree.update(..4, 2); // Add 2 to first half
    tree.update(2..6, 3); // Add 3 to middle section (overlaps)
    tree.update(4.., 1); // Add 1 to second half

    println!("After overlapping updates:");
    println!("Range [0, 2): sum = {}", tree.query(..2)); // (1+2) + (1+2) = 6
    println!("Range [2, 4): sum = {}", tree.query(2..4)); // (1+2+3) + (1+2+3) = 12
    println!("Range [4, 6): sum = {}", tree.query(4..6)); // (1+3+1) + (1+3+1) = 10
    println!("Range [6, 8): sum = {}", tree.query(6..)); // (1+1) + (1+1) = 4
    println!("Total sum: {}", tree.query(..)); // 6 + 12 + 10 + 4 = 32

    // Verify by querying individual ranges
    let mut total = 0;
    for i in 0..4 {
        let range_sum = tree.query(i * 2..(i + 1) * 2);
        total += range_sum;
        println!("  Range [{}, {}): {}", i * 2, (i + 1) * 2, range_sum);
    }
    println!("Sum verification: {}", total);
    println!();
}

pub fn query<R: RangeBounds<usize>>(&self, range: R) -> Spec::T

Query the range specified by range.

Returns the aggregate value over the specified range using the op_on_data operation. The range can be any type that implements RangeBounds<usize>, such as a..b, a..=b, ..b, a.., or ...

Time Complexity

O(log n)

Panics

Panics if the range is invalid (start > end) or out of bounds.

Examples

use array_range_query::{LazySegTree, LazySegTreeSpec};
let tree = LazySegTree::<RangeAddSum>::from_vec(&[1, 2, 3, 4, 5]);
assert_eq!(tree.query(1..4), 9);  // Sum of elements [2, 3, 4]
assert_eq!(tree.query(..), 15);   // Sum of all elements

Examples found in repository

examples/basic_usage.rs (line 161)

fn custom_lazy_example() {
    println!("4. Custom LazySegTree for Range Add + Range Sum");
    println!("----------------------------------------------");

    // Define a spec for range add operations with sum queries
    struct RangeAddSum;

    impl LazySegTreeSpec for RangeAddSum {
        type T = i64; // Data type (stores sums)
        type U = i64; // Update type (add values)
        const ID: Self::T = 0;

        // Combine two sum values
        fn op_on_data(d1: &mut Self::T, d2: &Self::T) {
            *d1 += *d2;
        }

        // Compose two add operations
        fn op_on_update(u1: &mut Self::U, u2: &Self::U) {
            *u1 += *u2;
        }

        // Apply add operation to sum (multiply by range size)
        fn op_update_on_data(u: &Self::U, d: &mut Self::T, size: usize) {
            *d += u * (size as i64);
        }
    }

    let values = vec![1i64, 2, 3, 4, 5];
    let mut lazy_tree = LazySegTree::<RangeAddSum>::from_vec(&values);

    println!("Initial values: {:?}", values);
    println!("Initial sum [1, 4): {}", lazy_tree.query(1..4)); // 2 + 3 + 4 = 9
    println!("Initial sum [0, 5): {}", lazy_tree.query(..)); // 15

    // Add 10 to all elements in range [1, 4)
    lazy_tree.update(1..4, 10);
    println!("\nAfter adding 10 to range [1, 4):");
    println!("Sum [1, 4): {}", lazy_tree.query(1..4)); // (2+10) + (3+10) + (4+10) = 39
    println!("Sum [0, 5): {}", lazy_tree.query(..)); // 1 + 12 + 13 + 14 + 5 = 45

    // Add 5 to range [0, 2)
    lazy_tree.update(..2, 5);
    println!("\nAfter adding 5 to range [0, 2):");
    println!("Sum [0, 2): {}", lazy_tree.query(..2)); // (1+5) + (12+5) = 23
    println!("Sum [0, 5): {}", lazy_tree.query(..)); // 6 + 17 + 13 + 14 + 5 = 55
    println!();
}

/// Example 5: Using LazySegTree helper types
fn lazy_helper_example() {
    println!("5. LazySegTree Helper Types");
    println!("--------------------------");

    // Range add + range sum
    let values = vec![2i32, 4, 6, 8, 10];
    let mut sum_tree = LazySegTreeAddSum::<i32>::from_vec(&values);

    println!("Initial values: {:?}", values);
    println!("Sum [0, 5): {}", sum_tree.query(..)); // 30
    println!("Sum [1, 4): {}", sum_tree.query(1..4)); // 4 + 6 + 8 = 18

    // Add 3 to range [1, 4)
    sum_tree.update(1..4, 3);
    println!("\nAfter adding 3 to range [1, 4):");
    println!("Sum [0, 5): {}", sum_tree.query(..)); // 2 + 7 + 9 + 11 + 10 = 39
    println!("Sum [1, 4): {}", sum_tree.query(1..4)); // 7 + 9 + 11 = 27

    // Add -2 to range [0, 3)
    sum_tree.update(..3, -2);
    println!("\nAfter subtracting 2 from range [0, 3):");
    println!("Sum [0, 5): {}", sum_tree.query(..)); // 0 + 5 + 7 + 11 + 10 = 33
    println!("Sum [0, 3): {}", sum_tree.query(..3)); // 0 + 5 + 7 = 12

    // Range add + range min
    let min_values = vec![5, 2, 8, 1, 9, 3];
    let mut min_tree = LazySegTreeAddMin::<i32>::from_vec(&min_values);
    println!("\nInitial min values: {:?}", min_values);
    println!("Min [0, 6): {}", min_tree.query(..)); // 1
    min_tree.update(1..4, 2);
    println!(
        "After adding 2 to [1, 4): Min [0, 6): {}",
        min_tree.query(..)
    ); // min(5, 4, 10, 3, 9, 3) = 3

    // Range assignment (replace) + range sum
    let rep_values = vec![1, 2, 3, 4, 5];
    let mut rep_tree = LazySegTreeReplaceSum::<i32>::from_vec(&rep_values);
    println!("\nInitial replace values: {:?}", rep_values);
    println!("Sum [0, 5): {}", rep_tree.query(..)); // 15
    rep_tree.update(1..4, 10); // Replace [1, 4) with 10
    println!(
        "After replacing [1, 4) with 10: Sum [0, 5): {}",
        rep_tree.query(..)
    ); // 1 + 10 + 10 + 10 + 5 = 36
    println!();
}

/// Example 6: Advanced lazy operations with overlapping updates
fn advanced_lazy_example() {
    println!("6. Advanced Lazy Operations");
    println!("--------------------------");

    let values = vec![1i32, 1, 1, 1, 1, 1, 1, 1]; // 8 ones
    let mut tree = LazySegTreeAddSum::<i32>::from_vec(&values);

    println!("Initial: 8 ones, sum = {}", tree.query(..));

    // Perform overlapping updates
    tree.update(..4, 2); // Add 2 to first half
    tree.update(2..6, 3); // Add 3 to middle section (overlaps)
    tree.update(4.., 1); // Add 1 to second half

    println!("After overlapping updates:");
    println!("Range [0, 2): sum = {}", tree.query(..2)); // (1+2) + (1+2) = 6
    println!("Range [2, 4): sum = {}", tree.query(2..4)); // (1+2+3) + (1+2+3) = 12
    println!("Range [4, 6): sum = {}", tree.query(4..6)); // (1+3+1) + (1+3+1) = 10
    println!("Range [6, 8): sum = {}", tree.query(6..)); // (1+1) + (1+1) = 4
    println!("Total sum: {}", tree.query(..)); // 6 + 12 + 10 + 4 = 32

    // Verify by querying individual ranges
    let mut total = 0;
    for i in 0..4 {
        let range_sum = tree.query(i * 2..(i + 1) * 2);
        total += range_sum;
        println!("  Range [{}, {}): {}", i * 2, (i + 1) * 2, range_sum);
    }
    println!("Sum verification: {}", total);
    println!();
}

pub fn update<R: RangeBounds<usize>>(&mut self, range: R, value: Spec::U)

Apply value lazily to the range specified by range.

Updates all elements in the specified range by applying the given update value. The range can be any type that implements RangeBounds<usize>.

Time Complexity

O(log n)

Panics

Panics if the range is invalid (start > end) or out of bounds.

Examples

use array_range_query::{LazySegTree, LazySegTreeSpec};
let mut tree = LazySegTree::<RangeAddSum>::from_vec(&[1, 2, 3, 4, 5]);
tree.update(1..4, 10); // Add 10 to elements at indices 1, 2, 3
assert_eq!(tree.query(..), 45); // 1 + 12 + 13 + 14 + 5

Examples found in repository

examples/basic_usage.rs (line 165)

fn custom_lazy_example() {
    println!("4. Custom LazySegTree for Range Add + Range Sum");
    println!("----------------------------------------------");

    // Define a spec for range add operations with sum queries
    struct RangeAddSum;

    impl LazySegTreeSpec for RangeAddSum {
        type T = i64; // Data type (stores sums)
        type U = i64; // Update type (add values)
        const ID: Self::T = 0;

        // Combine two sum values
        fn op_on_data(d1: &mut Self::T, d2: &Self::T) {
            *d1 += *d2;
        }

        // Compose two add operations
        fn op_on_update(u1: &mut Self::U, u2: &Self::U) {
            *u1 += *u2;
        }

        // Apply add operation to sum (multiply by range size)
        fn op_update_on_data(u: &Self::U, d: &mut Self::T, size: usize) {
            *d += u * (size as i64);
        }
    }

    let values = vec![1i64, 2, 3, 4, 5];
    let mut lazy_tree = LazySegTree::<RangeAddSum>::from_vec(&values);

    println!("Initial values: {:?}", values);
    println!("Initial sum [1, 4): {}", lazy_tree.query(1..4)); // 2 + 3 + 4 = 9
    println!("Initial sum [0, 5): {}", lazy_tree.query(..)); // 15

    // Add 10 to all elements in range [1, 4)
    lazy_tree.update(1..4, 10);
    println!("\nAfter adding 10 to range [1, 4):");
    println!("Sum [1, 4): {}", lazy_tree.query(1..4)); // (2+10) + (3+10) + (4+10) = 39
    println!("Sum [0, 5): {}", lazy_tree.query(..)); // 1 + 12 + 13 + 14 + 5 = 45

    // Add 5 to range [0, 2)
    lazy_tree.update(..2, 5);
    println!("\nAfter adding 5 to range [0, 2):");
    println!("Sum [0, 2): {}", lazy_tree.query(..2)); // (1+5) + (12+5) = 23
    println!("Sum [0, 5): {}", lazy_tree.query(..)); // 6 + 17 + 13 + 14 + 5 = 55
    println!();
}

/// Example 5: Using LazySegTree helper types
fn lazy_helper_example() {
    println!("5. LazySegTree Helper Types");
    println!("--------------------------");

    // Range add + range sum
    let values = vec![2i32, 4, 6, 8, 10];
    let mut sum_tree = LazySegTreeAddSum::<i32>::from_vec(&values);

    println!("Initial values: {:?}", values);
    println!("Sum [0, 5): {}", sum_tree.query(..)); // 30
    println!("Sum [1, 4): {}", sum_tree.query(1..4)); // 4 + 6 + 8 = 18

    // Add 3 to range [1, 4)
    sum_tree.update(1..4, 3);
    println!("\nAfter adding 3 to range [1, 4):");
    println!("Sum [0, 5): {}", sum_tree.query(..)); // 2 + 7 + 9 + 11 + 10 = 39
    println!("Sum [1, 4): {}", sum_tree.query(1..4)); // 7 + 9 + 11 = 27

    // Add -2 to range [0, 3)
    sum_tree.update(..3, -2);
    println!("\nAfter subtracting 2 from range [0, 3):");
    println!("Sum [0, 5): {}", sum_tree.query(..)); // 0 + 5 + 7 + 11 + 10 = 33
    println!("Sum [0, 3): {}", sum_tree.query(..3)); // 0 + 5 + 7 = 12

    // Range add + range min
    let min_values = vec![5, 2, 8, 1, 9, 3];
    let mut min_tree = LazySegTreeAddMin::<i32>::from_vec(&min_values);
    println!("\nInitial min values: {:?}", min_values);
    println!("Min [0, 6): {}", min_tree.query(..)); // 1
    min_tree.update(1..4, 2);
    println!(
        "After adding 2 to [1, 4): Min [0, 6): {}",
        min_tree.query(..)
    ); // min(5, 4, 10, 3, 9, 3) = 3

    // Range assignment (replace) + range sum
    let rep_values = vec![1, 2, 3, 4, 5];
    let mut rep_tree = LazySegTreeReplaceSum::<i32>::from_vec(&rep_values);
    println!("\nInitial replace values: {:?}", rep_values);
    println!("Sum [0, 5): {}", rep_tree.query(..)); // 15
    rep_tree.update(1..4, 10); // Replace [1, 4) with 10
    println!(
        "After replacing [1, 4) with 10: Sum [0, 5): {}",
        rep_tree.query(..)
    ); // 1 + 10 + 10 + 10 + 5 = 36
    println!();
}

/// Example 6: Advanced lazy operations with overlapping updates
fn advanced_lazy_example() {
    println!("6. Advanced Lazy Operations");
    println!("--------------------------");

    let values = vec![1i32, 1, 1, 1, 1, 1, 1, 1]; // 8 ones
    let mut tree = LazySegTreeAddSum::<i32>::from_vec(&values);

    println!("Initial: 8 ones, sum = {}", tree.query(..));

    // Perform overlapping updates
    tree.update(..4, 2); // Add 2 to first half
    tree.update(2..6, 3); // Add 3 to middle section (overlaps)
    tree.update(4.., 1); // Add 1 to second half

    println!("After overlapping updates:");
    println!("Range [0, 2): sum = {}", tree.query(..2)); // (1+2) + (1+2) = 6
    println!("Range [2, 4): sum = {}", tree.query(2..4)); // (1+2+3) + (1+2+3) = 12
    println!("Range [4, 6): sum = {}", tree.query(4..6)); // (1+3+1) + (1+3+1) = 10
    println!("Range [6, 8): sum = {}", tree.query(6..)); // (1+1) + (1+1) = 4
    println!("Total sum: {}", tree.query(..)); // 6 + 12 + 10 + 4 = 32

    // Verify by querying individual ranges
    let mut total = 0;
    for i in 0..4 {
        let range_sum = tree.query(i * 2..(i + 1) * 2);
        total += range_sum;
        println!("  Range [{}, {}): {}", i * 2, (i + 1) * 2, range_sum);
    }
    println!("Sum verification: {}", total);
    println!();
}

Trait Implementations

impl<Spec: Clone + LazySegTreeSpec> Clone for LazySegTree<Spec>

where Spec::T: Clone, Spec::U: Clone,

fn clone(&self) -> LazySegTree<Spec>

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<Spec: Debug + LazySegTreeSpec> Debug for LazySegTree<Spec>

where Spec::T: Debug, Spec::U: Debug,

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

Formats the value using the given formatter.

impl<Spec: LazySegTreeSpec> Display for LazySegTree<Spec>

where Spec::T: Display + PartialEq, Spec::U: Display,

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

Formats the value using the given formatter.