array_range_query

A high-performance, generic implementation of segment trees and lazy segment trees in Rust for efficient range queries and range updates.

Features

• Segment Tree: O(log n) point updates and range queries for any associative operation
• Lazy Segment Tree: O(log n) range updates and range queries with lazy propagation
• Generic Design: Type-safe specifications for custom operations
• Helper Types: Pre-built implementations for sum, min, max operations
• Zero-cost Abstractions: No runtime overhead from generics

Installation

cargo add array_range_query

Quick Start

Basic Segment Tree

use array_range_query::SegTreeSum;

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

assert_eq!(tree.query(1..4), 9); // Sum of [2, 3, 4]
tree.update(2, 10);              // Change index 2 to 10
assert_eq!(tree.query(..), 22);  // Total sum: 1+2+10+4+5

Lazy Segment Tree

use array_range_query::LazySegTreeAddSum;

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

assert_eq!(tree.query(1..4), 9); // Sum of [2, 3, 4]
tree.update(1..4, 10);           // Add 10 to range [1, 4)
assert_eq!(tree.query(..), 45);  // New total: 1+12+13+14+5

Helper Types

Regular Segment Trees

• SegTreeSum<T> — Range sum queries
• SegTreeMin<T> — Range minimum queries
• SegTreeMax<T> — Range maximum queries

Lazy Segment Trees

• LazySegTreeAddSum<T> — Range add updates, sum queries
• LazySegTreeAddMin<T> — Range add updates, min queries
• LazySegTreeAddMax<T> — Range add updates, max queries
• LazySegTreeReplaceSum<T> — Range assignment updates, sum queries

Custom Operations

Define your own operations by implementing the specification traits:

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 tree = SegTree::<MaxSpec>::from_vec(vec![3, 1, 4, 1, 5]);
assert_eq!(tree.query(..), 5); // Maximum element

For lazy segment trees:

use array_range_query::{LazySegTree, LazySegTreeSpec};

struct RangeAddSum;
impl LazySegTreeSpec for RangeAddSum {
    type T = i64; // Data type
    type U = i64; // Update type
    const ID: Self::T = 0;

    fn op_on_data(d1: &mut Self::T, d2: &Self::T) { *d1 += *d2; }
    fn op_on_update(u1: &mut Self::U, u2: &Self::U) { *u1 += *u2; }
    fn op_update_on_data(u: &Self::U, d: &mut Self::T, size: usize) {
        *d += u * size as i64;
    }
}

let mut tree = LazySegTree::<RangeAddSum>::from_vec(vec![1, 2, 3, 4, 5]);
tree.update(1..4, 10); // Add 10 to range [1, 4)
assert_eq!(tree.query(..), 45);

API Reference

SegTree

• new(size) / from_slice(values) / from_vec(values) — Construction
• query(range) — Range query in O(log n)
• update(index, value) — Point update in O(log n)

LazySegTree

• new(size) / from_slice(values) / from_vec(values) — Construction
• query(range) — Range query in O(log n)
• update(range, value) — Range update in O(log n)

Range Types

All query and update methods accept any range type:

• 2..5 (half-open)
• 2..=4 (inclusive)
• ..3 (from start)
• 2.. (to end)
• .. (entire range)

Performance

• Construction: O(n)
• Point update: O(log n)
• Range query: O(log n)
• Range update (lazy): O(log n)
• Space: O(n)

Requirements

• Rust 2021 edition
• Dependencies (for helpers): num-traits, min_max_traits

License

MIT License. See LICENSE for details.