Struct SegTree 

pub struct SegTree<Spec: SegTreeSpec> { /* private fields */ }

A generic Segment Tree data structure.

See SegTree for a detailed explanation and examples.

Implementations

impl<Spec: SegTreeSpec> SegTree<Spec>

pub fn new(size: usize) -> Self

Creates a new SegTree of a given size, initialized with identity elements.

The internal size of the tree will be the smallest power of two greater than or equal to size.

Time complexity: O(n) where n is the smallest power of two >= size.

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

Creates a new SegTree from a vector of initial values.

The tree is built 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 found in repository

examples/basic_usage.rs (line 53)

fn custom_sum_example() {
    println!("1. Custom SegTree for Sum Operations");
    println!("-----------------------------------");

    // Define a custom spec for sum operations
    struct SumSpec;

    impl SegTreeSpec for SumSpec {
        type T = i64;
        const ID: Self::T = 0; // Identity element for addition

        fn op(a: &Self::T, b: &Self::T) -> Self::T {
            a + b
        }
    }

    let values = vec![1, 2, 3, 4, 5];
    let mut seg_tree = SegTree::<SumSpec>::from_vec(&values);

    println!("Initial values: {:?}", values);
    println!("Sum of range [1, 4): {}", seg_tree.query(1, 4)); // 2 + 3 + 4 = 9
    println!("Sum of entire array [0, 5): {}", seg_tree.query(0, 5)); // 15

    // Update element at index 2 from 3 to 10
    seg_tree.update(2, 10);
    println!("\nAfter updating index 2 to 10:");
    println!("Sum of range [1, 4): {}", seg_tree.query(1, 4)); // 2 + 10 + 4 = 16
    println!("Sum of entire array [0, 5): {}", seg_tree.query(0, 5)); // 22
    println!();
}

/// Example 2: Using helper types for common operations
fn helper_types_example() {
    println!("2. Helper Types for Common Operations");
    println!("------------------------------------");

    let values = vec![3, 1, 4, 1, 5, 9, 2, 6, 5, 3];
    println!("Values: {:?}", values);

    // Sum operations
    let mut sum_tree = SegTreeSum::<i32>::from_vec(&values);
    println!("Range sum [2, 6): {}", sum_tree.query(2, 6)); // 4 + 1 + 5 + 9 = 19

    // Min operations
    let mut min_tree = SegTreeMin::<i32>::from_vec(&values);
    println!("Range min [2, 6): {}", min_tree.query(2, 6)); // min(4, 1, 5, 9) = 1

    // Max operations
    let mut max_tree = SegTreeMax::<i32>::from_vec(&values);
    println!("Range max [2, 6): {}", max_tree.query(2, 6)); // max(4, 1, 5, 9) = 9

    // Demonstrate updates
    println!("\nAfter updating index 3 to 20:");
    sum_tree.update(3, 20);
    min_tree.update(3, 20);
    max_tree.update(3, 20);

    println!("Range sum [2, 6): {}", sum_tree.query(2, 6)); // 4 + 20 + 5 + 9 = 38
    println!("Range min [2, 6): {}", min_tree.query(2, 6)); // min(4, 20, 5, 9) = 4
    println!("Range max [2, 6): {}", max_tree.query(2, 6)); // max(4, 20, 5, 9) = 20
    println!();
}

/// Example 3: Custom min operation with detailed explanation
fn custom_min_example() {
    println!("3. Custom Min Operation with Details");
    println!("-----------------------------------");

    struct MinSpec;

    impl SegTreeSpec for MinSpec {
        type T = i32;
        const ID: Self::T = i32::MAX; // Identity for min is maximum possible value

        fn op(a: &Self::T, b: &Self::T) -> Self::T {
            (*a).min(*b)
        }
    }

    let values = vec![7, 3, 9, 1, 6, 2, 8, 4];
    let seg_tree = SegTree::<MinSpec>::from_vec(&values);

    println!("Values: {:?}", values);
    println!("Min of entire array: {}", seg_tree.query(0, 8)); // 1
    println!("Min of [2, 5): {}", seg_tree.query(2, 5)); // min(9, 1, 6) = 1
    println!("Min of [0, 3): {}", seg_tree.query(0, 3)); // min(7, 3, 9) = 3
    println!("Min of [5, 8): {}", seg_tree.query(5, 8)); // min(2, 8, 4) = 2
    println!();
}

pub fn update(&mut self, index: usize, value: Spec::T)

Performs a point update, replacing the value at index with a new value.

After updating the leaf node, the change is propagated up the tree by recalculating the parent nodes.

Time complexity: O(log n).

Panics

Panics if index is out of bounds (index >= self.size).

Examples found in repository

examples/basic_usage.rs (line 60)

fn custom_sum_example() {
    println!("1. Custom SegTree for Sum Operations");
    println!("-----------------------------------");

    // Define a custom spec for sum operations
    struct SumSpec;

    impl SegTreeSpec for SumSpec {
        type T = i64;
        const ID: Self::T = 0; // Identity element for addition

        fn op(a: &Self::T, b: &Self::T) -> Self::T {
            a + b
        }
    }

    let values = vec![1, 2, 3, 4, 5];
    let mut seg_tree = SegTree::<SumSpec>::from_vec(&values);

    println!("Initial values: {:?}", values);
    println!("Sum of range [1, 4): {}", seg_tree.query(1, 4)); // 2 + 3 + 4 = 9
    println!("Sum of entire array [0, 5): {}", seg_tree.query(0, 5)); // 15

    // Update element at index 2 from 3 to 10
    seg_tree.update(2, 10);
    println!("\nAfter updating index 2 to 10:");
    println!("Sum of range [1, 4): {}", seg_tree.query(1, 4)); // 2 + 10 + 4 = 16
    println!("Sum of entire array [0, 5): {}", seg_tree.query(0, 5)); // 22
    println!();
}

/// Example 2: Using helper types for common operations
fn helper_types_example() {
    println!("2. Helper Types for Common Operations");
    println!("------------------------------------");

    let values = vec![3, 1, 4, 1, 5, 9, 2, 6, 5, 3];
    println!("Values: {:?}", values);

    // Sum operations
    let mut sum_tree = SegTreeSum::<i32>::from_vec(&values);
    println!("Range sum [2, 6): {}", sum_tree.query(2, 6)); // 4 + 1 + 5 + 9 = 19

    // Min operations
    let mut min_tree = SegTreeMin::<i32>::from_vec(&values);
    println!("Range min [2, 6): {}", min_tree.query(2, 6)); // min(4, 1, 5, 9) = 1

    // Max operations
    let mut max_tree = SegTreeMax::<i32>::from_vec(&values);
    println!("Range max [2, 6): {}", max_tree.query(2, 6)); // max(4, 1, 5, 9) = 9

    // Demonstrate updates
    println!("\nAfter updating index 3 to 20:");
    sum_tree.update(3, 20);
    min_tree.update(3, 20);
    max_tree.update(3, 20);

    println!("Range sum [2, 6): {}", sum_tree.query(2, 6)); // 4 + 20 + 5 + 9 = 38
    println!("Range min [2, 6): {}", min_tree.query(2, 6)); // min(4, 20, 5, 9) = 4
    println!("Range max [2, 6): {}", max_tree.query(2, 6)); // max(4, 20, 5, 9) = 20
    println!();
}

pub fn query(&self, left: usize, right: usize) -> Spec::T

Queries the segment tree for the aggregated value in the range [left, right).

The range is half-open, including left and excluding right.

Time complexity: O(log n).

Panics

This function panics if left > right or if right is out of the bounds of the original array size (right > self.size).

Examples found in repository

examples/basic_usage.rs (line 56)

fn custom_sum_example() {
    println!("1. Custom SegTree for Sum Operations");
    println!("-----------------------------------");

    // Define a custom spec for sum operations
    struct SumSpec;

    impl SegTreeSpec for SumSpec {
        type T = i64;
        const ID: Self::T = 0; // Identity element for addition

        fn op(a: &Self::T, b: &Self::T) -> Self::T {
            a + b
        }
    }

    let values = vec![1, 2, 3, 4, 5];
    let mut seg_tree = SegTree::<SumSpec>::from_vec(&values);

    println!("Initial values: {:?}", values);
    println!("Sum of range [1, 4): {}", seg_tree.query(1, 4)); // 2 + 3 + 4 = 9
    println!("Sum of entire array [0, 5): {}", seg_tree.query(0, 5)); // 15

    // Update element at index 2 from 3 to 10
    seg_tree.update(2, 10);
    println!("\nAfter updating index 2 to 10:");
    println!("Sum of range [1, 4): {}", seg_tree.query(1, 4)); // 2 + 10 + 4 = 16
    println!("Sum of entire array [0, 5): {}", seg_tree.query(0, 5)); // 22
    println!();
}

/// Example 2: Using helper types for common operations
fn helper_types_example() {
    println!("2. Helper Types for Common Operations");
    println!("------------------------------------");

    let values = vec![3, 1, 4, 1, 5, 9, 2, 6, 5, 3];
    println!("Values: {:?}", values);

    // Sum operations
    let mut sum_tree = SegTreeSum::<i32>::from_vec(&values);
    println!("Range sum [2, 6): {}", sum_tree.query(2, 6)); // 4 + 1 + 5 + 9 = 19

    // Min operations
    let mut min_tree = SegTreeMin::<i32>::from_vec(&values);
    println!("Range min [2, 6): {}", min_tree.query(2, 6)); // min(4, 1, 5, 9) = 1

    // Max operations
    let mut max_tree = SegTreeMax::<i32>::from_vec(&values);
    println!("Range max [2, 6): {}", max_tree.query(2, 6)); // max(4, 1, 5, 9) = 9

    // Demonstrate updates
    println!("\nAfter updating index 3 to 20:");
    sum_tree.update(3, 20);
    min_tree.update(3, 20);
    max_tree.update(3, 20);

    println!("Range sum [2, 6): {}", sum_tree.query(2, 6)); // 4 + 20 + 5 + 9 = 38
    println!("Range min [2, 6): {}", min_tree.query(2, 6)); // min(4, 20, 5, 9) = 4
    println!("Range max [2, 6): {}", max_tree.query(2, 6)); // max(4, 20, 5, 9) = 20
    println!();
}

/// Example 3: Custom min operation with detailed explanation
fn custom_min_example() {
    println!("3. Custom Min Operation with Details");
    println!("-----------------------------------");

    struct MinSpec;

    impl SegTreeSpec for MinSpec {
        type T = i32;
        const ID: Self::T = i32::MAX; // Identity for min is maximum possible value

        fn op(a: &Self::T, b: &Self::T) -> Self::T {
            (*a).min(*b)
        }
    }

    let values = vec![7, 3, 9, 1, 6, 2, 8, 4];
    let seg_tree = SegTree::<MinSpec>::from_vec(&values);

    println!("Values: {:?}", values);
    println!("Min of entire array: {}", seg_tree.query(0, 8)); // 1
    println!("Min of [2, 5): {}", seg_tree.query(2, 5)); // min(9, 1, 6) = 1
    println!("Min of [0, 3): {}", seg_tree.query(0, 3)); // min(7, 3, 9) = 3
    println!("Min of [5, 8): {}", seg_tree.query(5, 8)); // min(2, 8, 4) = 2
    println!();
}