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. Public operations:

• new(size) and from_vec(values) to construct,
• query(&self, left, right) to query [left, right),
• update(&mut self, left, right, value) to apply a lazy update to [left, right).

Implementations

impl<Spec: LazySegTreeSpec> LazySegTree<Spec>

pub fn new(size: usize) -> Self

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

max_size (the number of leaves used internally) will be the next power of two greater than or equal to size.

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

Build a tree from a slice of initial values. Complexity: O(n).

The slice length determines the logical size.

Examples found in repository

examples/basic_usage.rs (line 156)

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: &Self::T, d2: &Self::T) -> Self::T {
            d1 + d2
        }

        // Compose two add operations
        fn op_on_update(u1: &Self::U, u2: &Self::U) -> Self::U {
            u1 + u2
        }

        // Apply add operation to sum (multiply by range size)
        fn op_update_on_data(u: &Self::U, d: &Self::T, size: usize) -> Self::T {
            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(0, 5)); // 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(0, 5)); // 1 + 12 + 13 + 14 + 5 = 45

    // Add 5 to range [0, 2)
    lazy_tree.update(0, 2, 5);
    println!("\nAfter adding 5 to range [0, 2):");
    println!("Sum [0, 2): {}", lazy_tree.query(0, 2)); // (1+5) + (12+5) = 23
    println!("Sum [0, 5): {}", lazy_tree.query(0, 5)); // 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(0, 5)); // 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(0, 5)); // 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(0, 3, -2);
    println!("\nAfter subtracting 2 from range [0, 3):");
    println!("Sum [0, 5): {}", sum_tree.query(0, 5)); // 0 + 5 + 7 + 11 + 10 = 33
    println!("Sum [0, 3): {}", sum_tree.query(0, 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(0, 6)); // 1
    min_tree.update(1, 4, 2);
    println!(
        "After adding 2 to [1, 4): Min [0, 6): {}",
        min_tree.query(0, 6)
    ); // 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(0, 5)); // 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(0, 5)
    ); // 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(0, 8));

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

    println!("After overlapping updates:");
    println!("Range [0, 2): sum = {}", tree.query(0, 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, 8)); // (1+1) + (1+1) = 4
    println!("Total sum: {}", tree.query(0, 8)); // 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(&self, left: usize, right: usize) -> Spec::T

Query the half-open interval [left, right).

Returns Spec::ID for empty ranges (left == right). Panics if the range is invalid (see validate_range).

Examples found in repository

examples/basic_usage.rs (line 159)

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: &Self::T, d2: &Self::T) -> Self::T {
            d1 + d2
        }

        // Compose two add operations
        fn op_on_update(u1: &Self::U, u2: &Self::U) -> Self::U {
            u1 + u2
        }

        // Apply add operation to sum (multiply by range size)
        fn op_update_on_data(u: &Self::U, d: &Self::T, size: usize) -> Self::T {
            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(0, 5)); // 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(0, 5)); // 1 + 12 + 13 + 14 + 5 = 45

    // Add 5 to range [0, 2)
    lazy_tree.update(0, 2, 5);
    println!("\nAfter adding 5 to range [0, 2):");
    println!("Sum [0, 2): {}", lazy_tree.query(0, 2)); // (1+5) + (12+5) = 23
    println!("Sum [0, 5): {}", lazy_tree.query(0, 5)); // 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(0, 5)); // 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(0, 5)); // 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(0, 3, -2);
    println!("\nAfter subtracting 2 from range [0, 3):");
    println!("Sum [0, 5): {}", sum_tree.query(0, 5)); // 0 + 5 + 7 + 11 + 10 = 33
    println!("Sum [0, 3): {}", sum_tree.query(0, 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(0, 6)); // 1
    min_tree.update(1, 4, 2);
    println!(
        "After adding 2 to [1, 4): Min [0, 6): {}",
        min_tree.query(0, 6)
    ); // 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(0, 5)); // 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(0, 5)
    ); // 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(0, 8));

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

    println!("After overlapping updates:");
    println!("Range [0, 2): sum = {}", tree.query(0, 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, 8)); // (1+1) + (1+1) = 4
    println!("Total sum: {}", tree.query(0, 8)); // 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(&mut self, left: usize, right: usize, value: Spec::U)

Apply value lazily to the half-open interval [left, right).

Requires &mut self. Panics if range is invalid.

Examples found in repository

examples/basic_usage.rs (line 163)

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: &Self::T, d2: &Self::T) -> Self::T {
            d1 + d2
        }

        // Compose two add operations
        fn op_on_update(u1: &Self::U, u2: &Self::U) -> Self::U {
            u1 + u2
        }

        // Apply add operation to sum (multiply by range size)
        fn op_update_on_data(u: &Self::U, d: &Self::T, size: usize) -> Self::T {
            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(0, 5)); // 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(0, 5)); // 1 + 12 + 13 + 14 + 5 = 45

    // Add 5 to range [0, 2)
    lazy_tree.update(0, 2, 5);
    println!("\nAfter adding 5 to range [0, 2):");
    println!("Sum [0, 2): {}", lazy_tree.query(0, 2)); // (1+5) + (12+5) = 23
    println!("Sum [0, 5): {}", lazy_tree.query(0, 5)); // 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(0, 5)); // 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(0, 5)); // 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(0, 3, -2);
    println!("\nAfter subtracting 2 from range [0, 3):");
    println!("Sum [0, 5): {}", sum_tree.query(0, 5)); // 0 + 5 + 7 + 11 + 10 = 33
    println!("Sum [0, 3): {}", sum_tree.query(0, 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(0, 6)); // 1
    min_tree.update(1, 4, 2);
    println!(
        "After adding 2 to [1, 4): Min [0, 6): {}",
        min_tree.query(0, 6)
    ); // 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(0, 5)); // 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(0, 5)
    ); // 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(0, 8));

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

    println!("After overlapping updates:");
    println!("Range [0, 2): sum = {}", tree.query(0, 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, 8)); // (1+1) + (1+1) = 4
    println!("Total sum: {}", tree.query(0, 8)); // 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.