Struct SegTree 

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

A generic Segment Tree data structure.

A segment tree is a complete binary tree stored in a flat array that enables efficient range queries and point updates on sequences of elements. The tree supports any associative operation defined by the SegTreeSpec trait.

Internal Structure

• Uses 1-based indexing where the root is at index 1
• Leaf nodes start at index max_size (next power of 2 ≥ size)
• For any node at index i, its children are at 2*i and 2*i+1
• Total space used is 2 * max_size

Type Parameters

• Spec - A type implementing SegTreeSpec that defines the operation and element type

Examples

use array_range_query::{SegTree, SegTreeSpec};

struct MaxSpec;
impl SegTreeSpec for MaxSpec {
    type T = i32;
    const ID: Self::T = i32::MIN;
    fn op(a: &mut Self::T, b: &Self::T) { *a = (*a).max(*b); }
}

let values = vec![3, 1, 4, 1, 5, 9, 2];
let tree = SegTree::<MaxSpec>::from_vec(&values);
assert_eq!(tree.query(2..5), 5); // max(4, 1, 5) = 5

Implementations

impl<Spec: SegTreeSpec> SegTree<Spec>

pub fn new(size: usize) -> Self

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

All elements in the tree are initialized to Spec::ID. The internal tree size (max_size) will be the smallest power of two greater than or equal to size for optimal tree structure and performance.

Time Complexity

O(n) where n is the smallest power of two ≥ size.

Examples

use array_range_query::{SegTree, SegTreeSpec};

struct SumSpec;
impl SegTreeSpec for SumSpec {
    type T = i64;
    const ID: Self::T = 0;
    fn op(a: &mut Self::T, b: &Self::T) { *a += *b; }
}

let tree = SegTree::<SumSpec>::new(100);
assert_eq!(tree.query(..), 0); // All elements are 0 (identity)

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 using a bottom-up approach, which is more efficient than creating an empty tree and updating each element individually. This is the recommended way to initialize a segment tree with known values.

Time Complexity

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

Examples

use array_range_query::{SegTree, SegTreeSpec};

struct SumSpec;
impl SegTreeSpec for SumSpec {
    type T = i64;
    const ID: Self::T = 0;
    fn op(a: &mut Self::T, b: &Self::T) { *a += *b; }
}

let values = vec![1, 2, 3, 4, 5];
let tree = SegTree::<SumSpec>::from_vec(&values);
assert_eq!(tree.query(..), 15); // Sum of all elements
assert_eq!(tree.query(1..4), 9); // Sum of elements [2, 3, 4]

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: &mut Self::T, b: &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(..)); // 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(..)); // 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: &mut Self::T, b: &Self::T) {
            if *a > *b {
                *a = *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(..)); // 1
    println!("Min of [2, 5): {}", seg_tree.query(2..5)); // min(9, 1, 6) = 1
    println!("Min of [0, 3): {}", seg_tree.query(..3)); // min(7, 3, 9) = 3
    println!("Min of [5, 8): {}", seg_tree.query(5..)); // min(2, 8, 4) = 2
    println!();
}

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

Creates a new SegTree from a mutable vector of initial values.

Similar to from_vec, but takes a mutable reference to the input values. This can be useful when you already have a mutable reference and want to avoid additional borrowing constraints.

Time Complexity

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

Examples

use array_range_query::{SegTree, SegTreeSpec};

struct SumSpec;
impl SegTreeSpec for SumSpec {
    type T = i64;
    const ID: Self::T = 0;
    fn op(a: &mut Self::T, b: &Self::T) { *a += *b; }
}

let mut values = vec![1, 2, 3, 4, 5];
let tree = SegTree::<SumSpec>::from_mut_vec(&mut values);
assert_eq!(tree.query(..), 15);

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

Queries the segment tree for the aggregated value in the given range.

Returns the result of applying the monoid operation across all elements in the specified range. 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

• If the start of the range is greater than the end
• If the end of the range is out of bounds (> self.size)

Examples

use array_range_query::{SegTree, SegTreeSpec};

struct SumSpec;
impl SegTreeSpec for SumSpec {
    type T = i64;
    const ID: Self::T = 0;
    fn op(a: &mut Self::T, b: &Self::T) { *a += *b; }
}

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

assert_eq!(tree.query(..), 15);      // All elements: 1+2+3+4+5
assert_eq!(tree.query(1..4), 9);     // Elements [1,4): 2+3+4
assert_eq!(tree.query(2..=4), 12);   // Elements [2,4]: 3+4+5
assert_eq!(tree.query(..3), 6);      // Elements [0,3): 1+2+3
assert_eq!(tree.query(2..), 12);     // Elements [2,∞): 3+4+5

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: &mut Self::T, b: &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(..)); // 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(..)); // 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: &mut Self::T, b: &Self::T) {
            if *a > *b {
                *a = *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(..)); // 1
    println!("Min of [2, 5): {}", seg_tree.query(2..5)); // min(9, 1, 6) = 1
    println!("Min of [0, 3): {}", seg_tree.query(..3)); // min(7, 3, 9) = 3
    println!("Min of [5, 8): {}", seg_tree.query(5..)); // 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 all ancestor nodes. This maintains the tree invariant that each internal node contains the aggregate of its subtree.

Time Complexity

O(log n)

Panics

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

Examples

use array_range_query::{SegTree, SegTreeSpec};

struct SumSpec;
impl SegTreeSpec for SumSpec {
    type T = i64;
    const ID: Self::T = 0;
    fn op(a: &mut Self::T, b: &Self::T) { *a += *b; }
}

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

assert_eq!(tree.query(..), 15);  // Original sum

tree.update(2, 10);              // Change 3 to 10
assert_eq!(tree.query(..), 22);  // New sum: 1+2+10+4+5
assert_eq!(tree.query(2..3), 10); // Just the updated element

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: &mut Self::T, b: &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(..)); // 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(..)); // 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!();
}