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 segment tree with all elements initialized to Spec::ID.

Time Complexity

O(n)

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

Creates a new segment tree from a slice of values.

Time Complexity

O(n)

pub fn from_vec(vec: Vec<Spec::T>) -> Self

Creates a new segment tree from a vector of values.

Time Complexity

O(n)

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

Queries the aggregated value over the given range.

Example

use array_range_query::helpers::SegTreeMax;

let mut tree = SegTreeMax::<i32>::from_vec(vec![1, 2, 3, 4, 5]);
assert_eq!(tree.query(..), 5);

Time Complexity

O(log n)

Panics

Panics if the range is invalid or out of bounds.

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

Updates the value at the given index.

Example

use array_range_query::helpers::SegTreeMax;

let mut tree = SegTreeMax::<i32>::from_vec(vec![1, 2, 3, 4, 5]);
assert_eq!(tree.query(..), 5);
tree.update(2, 6);
assert_eq!(tree.query(..), 6);

Time Complexity

O(log n)

Panics

Panics if index is out of bounds.